Towers of Hanoi and analysis of algorithms.

*(English)*Zbl 0589.90086We exemplify the analysis of algorithms by considering the Towers of Hanoi problem. The three-fold task of analysis of algorithms is (1) to produce provably correct algorithms, (2) to compare algorithms on the basis of how much of a resource, e.g. time or space, they use, (3) to prove lower bounds on the complexity of problems.

We begin by considering the well-known recursive algorithm for Towers of Hanoi. We prove this algorithm correct, and use this result to show a \(\theta (2^ n)\) lower bound on the running time of any algorithm which solves the n disk problem. From this running time bound we derive a space lower bound of \(n+cons\tan t\) bits.

Returning to the recursive algorithm we show that it uses \(\theta\) (n log n) bits. By unwinding the recursion we identify space usage which is unnecessary, and thereby produce an iterative algorithm which uses \(\theta\) (n) bits. To reduce the space usage to \(n+\)constant bits we note a number of facts about the Towers of Hanoi problem, e.g. all odd numbered disks move in one direction while all even numbered disks move in the opposite direction. We use these facts to create a 12 line algorithm, TOWERS. We demonstrate that TOWERS correctly solves the Towers of Hanoi problem for n disks using \(\theta (2^ n)\) time and \(n+\)constant bits of space, and hence that TOWERS is a best algorithm for this problem.

We conclude by giving two other Towers of Hanoi algorithms, and ask the interested reader to prove the correctness and analyze the time and space used by these algorithms.

We begin by considering the well-known recursive algorithm for Towers of Hanoi. We prove this algorithm correct, and use this result to show a \(\theta (2^ n)\) lower bound on the running time of any algorithm which solves the n disk problem. From this running time bound we derive a space lower bound of \(n+cons\tan t\) bits.

Returning to the recursive algorithm we show that it uses \(\theta\) (n log n) bits. By unwinding the recursion we identify space usage which is unnecessary, and thereby produce an iterative algorithm which uses \(\theta\) (n) bits. To reduce the space usage to \(n+\)constant bits we note a number of facts about the Towers of Hanoi problem, e.g. all odd numbered disks move in one direction while all even numbered disks move in the opposite direction. We use these facts to create a 12 line algorithm, TOWERS. We demonstrate that TOWERS correctly solves the Towers of Hanoi problem for n disks using \(\theta (2^ n)\) time and \(n+\)constant bits of space, and hence that TOWERS is a best algorithm for this problem.

We conclude by giving two other Towers of Hanoi algorithms, and ask the interested reader to prove the correctness and analyze the time and space used by these algorithms.