I have developed the activity sheets below 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.
This problem is described in several places and is often used as an introductory example of dynamic programming.
Four-page version including maximum, minimum, sequence alignment: pdf
Maximum and minimum problems on the same page, many times over: pdf Print two copies of each, have students solve them individually, then find the other student with the same scenario to compare solutions.
Challenge: Write a computer program to generate random edge scores and solve the Manhattan tourist problem.
(Some links are missing in the lines below, email zirbel@bgsu.edu if you want to see them)
Matlab program to generate single problems and show the solution. You will also need this program by Erik Johnson to draw arrows.
Matlab program to generate multiple pages with maximum and minimum problems.
After this activity, it can be easily related to the minimum-distance problems solved by GPS navigators. It is helpful to display a map of the US interstate system and suggest making a route from Northwest (Seattle) to Southeast (Atlanta). Some useful maps are: road map, grid form, grid form, US rail network.
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.
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).
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.