(a) Program the recursive algorithm for the Towers of Hanoi.
Program one of the iterative algorithms for the Towers of Hanoi. (see NOTES ) Clearly state which iterative algorithm you are using.
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.
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.
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 a ected by I/O time.
Plot the running times for both programs as a function of n.
If the running times are approximated by C2n, estimate the value of C. You will have two C’s, one for the recursive program and one for the iterative program.
Which algorithm will be faster for large values of n?
Estimate the time it would take each program to solve the Towers of Hanoi with 64 disks.
Estimate the largest Towers of Hanoi problem your programs could solve in 10 minutes on the computer you used.
