Dynamic programming activities

I have developed these activity sheets for use with a variety of student groups ranging from junior-high students who are on a university campus for a day to new freshmen to seniors, master's students, and PhD students.  Nearly all students find these ideas to be new and interesting.  The mathematical level is quite modest, usually only requiring addition and the identification of the maximum of two or three numbers.  They are designed to be done as activities with some guidance from the leader of the group.

All activities can be downloaded in Word and PDF format.  Feel free to use them.  It is OK to alter them, but if you do, I would appreciate it if you would leave the line "Developed by Craig L. Zirbel" and add the text "and modified by ...".  If you develop something new, I would be interested in posting a link to it here.

The main point of these activities is that some "large" problems look impossible to solve, but very "small" versions of the same problem can be solved quite easily.  When solutions of small problems can be easily assembled into solutions of larger problems, one can imagine solving the original problem by iteratively solving all smaller problems.  This may be tedious for a human, but a computer can solve it very quickly.

Manhattan tourist problem

This problem is described in several places and is often used as an introductory example of dynamic programming.

Chips game

This is a version of the Game of Nim, in which two players take turns removing poker chips from two piles, obeying certain rules.  Starting with many chips makes it hard to predict who will win, but starting with just a few makes it easy.

Making change with unusual coins

How can you make change with 1 cent, 4 cent, and 6 cent coins?  This activity is simpler than the ones above in that it requires the solution of fewer smaller problems (they can be arranged along a line rather than filling in a grid). 

Sequence alignment in bioinformatics

Given two similar sequences of letters, how can we insert spaces so that, when written out one above the other, we see the largest number of matching letters?  The Manhattan tourist problem is often used as motivation for the alignment problem.  This activity starts very much focused on sequences, but then gives way to a simpler implementation which is just about recording the maximum number of matching letters.