CS 325
Homework #2
The Towers of Hanoi
1. (a) Program the recursive algorithm for the Towers of Hanoi.
(b) Program one of the iterative algorithms for the Towers of Hanoi. (see NOTES )
Clearly state which iterative algorithm you are using.
2. Use both your programs to print out the correct solution sequences of moves for 3 and
4 disks. Verify that your programs produce the correct sequences to solve the puzzle.
3. Either by hand or by use of your recursive program, write out the succesive contents
of the recursion stack as your recursive program solves the Towers of Hanoi for 4 disks.
4. Run and time your programs for various small values of n where n is the number of
disks. Suppress printing for these timing runs so algorithm timing is not adversely
affected by I/O time.
5. Plot the running times for both programs as a function of n.
6. If the running times are approximated by C2
n
, estimate the value of C. You will have
two C’s, one for the recursive program and one for the iterative program.
7. Which algorithm will be faster for large values of n?
8. Estimate the time it would take each program to solve the Towers of Hanoi with 64
disks.
9. Estimate the largest Towers of Hanoi problem your programs could solve in 10 minutes
on the computer you used.
