2-in-1 with the jump-it game
Jamil M. Saquer, Razib Iqbal · Journal of computing sciences in colleges · 2017
The concept of recursion lies at the core of many modern programming languages and it is applied to many data structures like lists and trees. On the other hand, the core concept behind a dynamic programming algorithm is to store the results of smaller sub-problems and look them up when they are needed later to solve larger sub-problems instead of re-computing the smaller sub-problems over and over again. Well known algorithms textbooks (e.g. [5, 6]) use the 0--1 knapsack problem, matrix-chain multiplication, and other classical examples to introduce dynamic programming to students. Nonetheless, many students find these problems uninteresting and sometimes difficult to understand. Shortage of interesting problems when introducing dynamic programming to students leads to the shortcomings of grasping the technique to apply it to other real life scenarios. This paper introduces an interesting example, the Jump-It game, which can be used to teach dynamic programming to students. This example can also be used when teaching recursion in the CS1 and CS2 classes.