Consider the following variant of the Tower of Hanoi puzzle. As in the original puzzle, you have three pegs, numbered 0, 1, and 2, and you have n disks on peg 0 that are to be moved to peg 2, subject to the constraint that only one disk can be moved at a time, from one peg to another, and that no disk is allowed to be on top of a smaller disk (this last constraint is also satisfied initially). Unlike the original puzzle, however, now the pegs are arranged in a circular fashion, as 0-1-2 in counterclockwise order, and you are onlyallowed to move disks counterclockwise. See figure.

(a) Develop a divide and conquer algorithm for solving this problem. Although we do not explicitly require a proof of correctness for your algorithm, you will receive full points only if your algorithm satisfies all requirements for the problem. Hint: Note that for this variant, moving a disk one place counterclockwise can be different from moving it two places counterclockwise. We recommend writing two different procedures for these two operations and linking them through recursive calls.

(b) Analyze the asymptotic number of moves your algorithm makes. For full points, your algorithm should make O(3n) moves.

A top view of the first eight moves in a counterclockwise Towers of Hanoi solution A top view of the first eight moves in a counterclockwise Towers of Hanoi solution