Computer Science Open Days

A demonstration of a programming problem for first year students.

The world of computer science offers many challenging problems in designing algorithms to programme a computer. Sophisticated algorithms now exist for tasks such as, cryptography, data compression, and image processing. But before our students at Warwick can address such interesting applications they would first have to master the basic programming problems and methods. In this demonstration we study one such problem and a standard technique to solve it.

### The towers of Hanoi

Suppose I have a number of rings on a pole and I want to move them all to another pole one by one. The constraint is that no larger ring may at any time rest on a smaller ring.

When my initial pile has one, two, or three rings you can probably work out hot to solve the problem in each such case. But clearly the more rings there are the harder it gets to solve the problem in each case. It if you don't believe it why not try the Javalovers demo on the web at http://www.javalovers.com/hanoi.htm. So what if I want to write a program which will work for any pile of rings however large. We need an algorithm which will work for an arbitrarily large pile of rings.

### Divide and conquer your problems!

Not only is this good advice for solving lots of our everyday problems it is also one of the most basic tools for solving problems on a computer. Break your problem into its subproblems, solve each sub problem, then combine those solutions to solve the original problem. In applying this method to the towers of Hanoi we break the problem of moving n rings (in our example here it is 5) into two sub problems, each of how to move n-1 rings. This is the technique known as recursion where a problem of 'size' n is broken down into problem(s) of size some number less than n (more often than not n-1). Problems get repeatedly broken down into smaller problems until we reach the so called 'base case' where (typically n=1) we can solve the problem by trivial or other means. The Hanoi problem for one ring is clearly trivial. Here now is the recrusive solution to the Hanoi problem for 5 rings.

### How do we code up this recursive algorithm in a programming language ?

There is a bit more to think about when defining our 'n-problem' for the Hanoi towers than just saying we need to move n rings, we also need to know from which pole and to which pole the rings are moved. Let us name the poles 1, 2, and 3. Then the problem is to recursively define the sequence of actions to move n rings from any pole a to any other pole b.

if   n=1   then     move one ring from pole   a   to pole   b
else   move   n-1   rings from pole   a   to pole   6-a-b
move one ring from pole   a   to pole   b
move   n-1   rings from pole   6-a-b   to pole   b

This algorithm is expressed here in English, but first year students here at Warwick would be asked to write it in the Java programming language.

### How does the computer execute this program ?

This is an interesting question, as how can the computer be half way through solving a problem such as,   move 5 rings from pole 1 to pole 3   in order to start the new smaller problem,   move 4 rings from pole 2 to pole 3 ? Would it not have to stop working on one problem in order to start working on another ? The answer is that the computer suspends working on the larger problem while it solves the smaller one. For any   n   there are   2n-1-1   problems to start and then suspend in solving the Hanoi problem for   n   rings. Thus for the 5 ring problem we need to keep track of 15 suspended problems. This is why the Hanoi problem is too hard for most humans to solve when n exceeds 4; human memory is just too unreliable compared with that of a computer. In this modern age we no longer have to know how to move the rings, but rather how to instruct a machine to do it for us, and that is the wonderous challenge of programming!