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.