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
  
  

Talking Shop

During my first few years teaching computer science, I frequently felt isolated. As pretty much the only CS guy I really didn't have any one to "talk shop" with. It's hard to bounce pedagogical ideas off of your colleagues when they teach subjects that are tangentially related, at best.

I now consider myself extremely fortunate that I have four terrific friends and colleagues teaching CS with me. Now we have the same advantage that other teachers have enjoyed for years.

Today I started one of my favorite topics in my AP classes, recursion. Our students have already done recursion during the scheme unit of our intro class so today was at some levels, a review. Most of the students were fine with the basic concepts, but I wanted to make sure they had a solid foundation before we moved to more advanced problems.

I realized even though I "got" recursion back when I was starting out as a CS student those many years ago, no one ever really explained how the call stack worked. When you're calling functions and methods all over the place, how does the system know to return to the right place at the right time. It was alluded to when we expanded a recursion:

fact(4) –> 4*fact(3) –> 3*fact(2) –> 2*fact(1) –> 1*fact(0) –> 1

but never in the general sense of function calls. I thought it might make sense to try to "demystify" the computer and explain how things really worked.

I outlined a basic memory layout, stack, heap, data segment and roughly defined a stack frame (storing parameters, local variables, and a return address). We then looked at a code snippet such as:

a()
{
  b();
  c();
}

b()
{
  c();
}

c()
{
}

main()
{
  a();
  b();
}

and traced through the stack. We then did this with a couple of simple recursive examples. Only time will tell if this was helpful, but I think it was worth the time.

What I particularly enjoyed was later that day when I was talking shop with my fellow AP teacher. He wasn't planning on explaining the stack in this kind of detail but he liked the idea and planned to use that part of my lesson. I look forward to hearing how it went.

I have likewise borrowed ideas from his and our other colleagues classes.

Any CS teachers out there, I'm sure we'd all love to hear classroom techniques that have and haven't worked.