JE Exercise
5 (a) [3 points]
(b) [6 points]
(c) [6 points]
Consider the following more complex variant of the Tower of Hanoi puzzle
The puzzle has a row of k pegs, numbered from 1 to k. In a single turn, you
are allowed to move the smallest disk on peg i to either peg i − 1 or peg i + 1,
for any index i; as usual, you are not allowed to place a bigger disk on a
smaller disk. Your mission is to move a stack of n disks from peg 1 to peg k.
(a) Describe a recursive algorithm for the case k = 3. Exactly how many
moves does your algorithm make? (This is exactly the same as problem
4(a).)
(b) Describe a recursive algorithm for the case k = n + 1 that requires at
most O(n^3) moves. [Hint: Use part (a).]
(c) Describe a recursive algorithm for the case k = n + 1 that requires at
most O(n^2) moves. [Hint: Don’t use part (a).]
For all the algorithms, give a pseudocode (optional), an explanation in English (if needed, add a figure of a generic example ... in terms of n, not an example with, say, 6 disks), and a complexity analysis using a recurrence relation. Your algorithms should involve recursive calls.