Towers of Hanoi

Closed out last week teaching the Towers of Hanoi. It's a wonderful topic. Not because it's so interesting in and of itself, but as a platform from which you can explore any number of interesting topics.

Many books appropriate for the AP (AB) curriculum mention the towers, but to my knowledge most only scratch the surface. I randomly grabbed two books that I consider good from the shelf before writing this. One that I actually use when I teach AP comp sci and another more appropriate for a follow up course. Both discuss the towers, but merely show a solution and talk about the run time a little.

So many possibilities left out.

I usually do these lessons with my sophomores but since many of my AP students (juniors) hadn't ever seened the problem, I felt it was worth covering.

By looking at a few small examples, 1 disk, two disks, three disks, four disks, it's easy to notice the symetry in the solutions ultimately leading the this short routine:

 1:  hanoi(n,src,dst,tmp) {
 2:    if (n==1)
 3:      System.out.println("Move from "+src+" to "+dst);
 4:    else
 5:    {
 6:      hanoi(n-1,src,tmp.dst);
 7:      hanoi(1,src,dst,tmp);
 8:      hanoi(n-1,tmp,dst,src);
 9:    }
10:  }  

Now, the fun can really start:

We want to talk about the correctness of our algorithm and also how many moves it will take, that is, the run time. First, we'll use inductive ideas to show our algorithm is correct. This "proof" (we do it somewhat informally) can be enlightening. As sophomores, the only proofs students have seen are those statement/reason things they do in math class. Here we can introduce them to the idea that proof is just an "irrefutable argument" and apply it in a more practical setting.

From there we look at run time, that is, how many moves will it take to solve the n disk problem. It's easy to see the pattern of T(N) = 2T(n-1)+1 . Students will usually see that we can rewrite this as T(N)=2^N-1 which we can also prove by induction.

Now we can see the ramifications of the run time. At 1 million moves per second, it works out to close to 600,000 years. This in and of itself is revealing, we can't just "get a faster computer." Here we can discuss Moore's Law and the physical limits on our computers, making sure to make appropriate reference to Grace Hopper and her nanosecond.

This leads to a discussion alternate approaches such as parallel processing, but that doesn't work if our problem can only be solved sequentially.

The rest of the class is used discussing other hard problems and other approaches including heuristics, probabalistic, randomized, and anything else that comes up.

So, there you have it. From this one simple problem we get to introduce students to:

• Alternate forms of proof (specificall induction)
  
• Intractable problems
  
• Unsolvable problem
  
• Moores law and the limits of our computing power
  
• Alternate approaches to computing  
  
  
  
  • Parallel programming
    
  • Protein based computers
    
  • Randomized algorithms
    
  • Probabalistic algorithms
    
  • Heuristics