Suppose that we modify the Tower of Hanoi puzzle so that moves between the left peg to the right peg are disallowed: you may make moves only between the left and middle pegs, or between the middle and right pegs.
Is it still possible to move N disks from the left to the right peg in this case? If so, (a) write a procedure that reads an integer N and prints out a sequence of moves to perform this task; (b) determine the big-O running time of this procedure.
Consider another modified Hanoi in which moves are allowed only from A to B, from B to C and from C to A, where A, B and C are the left, midle and right pegs. Moves in the opposite direction (e.g. from B to A) are not allowed.
Is it still possible to move N disks from the left to right peg (A to C) in this case? If so, (a) write a program that reads an integer N and prints out a sequence of moves to perform this task; (b) determine the big-O running time of this procedure.
Solve the recurrence T(n) = 4 T(n / 2) + O(n), producing a closed form in big-O notation. Hint: use a recursion tree.
Solve the recurrence T(n) = 2 T(n / 4) + O(sqrt(n)).
Solve the recurrence T(n) = 2 T(n / 4) + O(n).