Tower of Hanoi
The Tower of Hanoi is a well known mathematical puzzle. It consists of three rods, and a number n of disks of different sizes which can slide onto any rod. The puzzle starts with all disks stacked up on the 1st rod in order of increasing size with the smallest on top. The objective of the puzzle is to move all the disks to the 3rd rod, while obeying the following rules. . Only one disk is moved at a time Each move consists of taking one disk from top of a rod, and moving it on top of the stack on another rod . No disk may be placed on top of a smaller disk. A recursive algorithm that solves this problem is as follows: We first move the top n - 1 disks from rod 1 to rod 2. Then we move the largest disk from rod 1 to rod 3 and then move the n- 1 smaller disks from rod 2 to rod 3. Using the symmetry between the rods, the number of steps that this algorithm takes is given by the recurrence T(n) = 2T(n-1) + 1 which can be solved to get T(n)-2"-1. (a) (5 points) Show that the above algorithm is optimal, i.e., there does not exist a strategy that (b) (5 points) Suppose the moves are restricted further such that you are only allowed to move (c) (6 points(Extra credit)) Suppose the moves are restricted such that you are only allowed to solves the Tower of Hanoi puzzle in less than 2n - 1 steps disks to and from rod 2. Give an algorithm that solves the puzzle in O(3") steps. move from rod 1 to rod 2, rod 2 to rod 3, and from rod 3 to rod 1. Give an algorithm that solves the puzzle in O(1 V3)") steps. The Tower of Hanoi is a well known mathematical puzzle. It consists of three rods, and a number n of disks of different sizes which can slide onto any rod. The puzzle starts with all disks stacked up on the 1st rod in order of increasing size with the smallest on top. The objective of the puzzle is to move all the disks to the 3rd rod, while obeying the following rules. . Only one disk is moved at a time Each move consists of taking one disk from top of a rod, and moving it on top of the stack on another rod . No disk may be placed on top of a smaller disk. A recursive algorithm that solves this problem is as follows: We first move the top n - 1 disks from rod 1 to rod 2. Then we move the largest disk from rod 1 to rod 3 and then move the n- 1 smaller disks from rod 2 to rod 3. Using the symmetry between the rods, the number of steps that this algorithm takes is given by the recurrence T(n) = 2T(n-1) + 1 which can be solved to get T(n)-2"-1. (a) (5 points) Show that the above algorithm is optimal, i.e., there does not exist a strategy that (b) (5 points) Suppose the moves are restricted further such that you are only allowed to move (c) (6 points(Extra credit)) Suppose the moves are restricted such that you are only allowed to solves the Tower of Hanoi puzzle in less than 2n - 1 steps disks to and from rod 2. Give an algorithm that solves the puzzle in O(3") steps. move from rod 1 to rod 2, rod 2 to rod 3, and from rod 3 to rod 1. Give an algorithm that solves the puzzle in O(1 V3)") steps
