Wednesday, October 1, 2008

Score one for induction!

One of my favorite textbooks on algorithms—in spite of the fact that it's twenty years old—is Udi Manber's Introduction to Algorithms: A Creative Approach. However, I have never been tempted to actually use it in class. You see, the book's greatest strength is also its greatest weakness.

Most textbooks on algorithms show you a lot of polished algorithms, but provide little or no insight on how to go about designing such algorithms. Manber's book does a very good job providing such insight, by making an analogy with inductive proofs. If you have any skill with induction, then you can use Manber's approach to help you design algorithms. (Of course, this should come as no surprise since writing an inductive proof and writing a recursive function are essentially the same activity.)

I'm sure you see the flaw here—most students are even less comfortable with induction than they are with recursion. It's like trying to help somebody learn to drive a car by making an analogy with riding a unicycle. For a certain segment of the audience, that analogy might be just what they need, but for the most of the audience, the analogy will only produce puzzled looks.

I was recently helping a student who was struggling to get a handle on recursion. He was making the common beginner mistake of trying to think about what happens during the recursive call instead of trusting that the recursive call works (sometimes called the recursive leap of faith). By sheer coincidence, I had happened to notice the day before that this student had done very well in our discrete math course the previous year. Time to give it a try...

“You know when you're writing a proof by induction and at some point you use the inductive hypothesis? That's just like a recursive call. You don't worry about what happens inside the inductive hypothesis, you just say ‘Assume that it works for N-1...’ It's the same with recursion. You just assume that the recursive call works.”

That comparison actually seemed to help. Maybe Manber was onto something after all!

7 comments:

Rob said...

That sounds like an interesting book, I will have to take a look!

I have become interested lately in the reverse direction - I encounter many competent ML hackers that do not understand proofs, and I was interested in exploring teaching proofs by analogy to recursive programming. Do you know of any similar sources that teach this analogy?

Omar said...

I've explained writing recursive functions as analogous to proving things by induction to two different math students with great, even instant, success. Of course, my CS students tend to not understand induction, so I see the problem you mention...

Benjamin said...

I've had the reverse experience. I already grokked recursion when I was introduced to proof by induction. The analogy to programming made learning the math much easier.

Udi said...

It's very rewarding to read this 20 years later. You are right, of course, that many students do not get it. That was my experience too. But many do. And for those, this is a powerful way of thinking that will improve their skills and their understanding. If I were to write this text again, I would not devote the whole course to this one technique, but spend most of the time on the use of practical algorithms -- like hashing -- and on developing the right intuition on how to use them in today's large scale distributed environments that we didn't have 20 years ago.

biokinetic said...

yeah, that's the book and the approach we used when i took my Algorithms course at Purdue 4 years ago. I can't say it was an easy way to learn but once you get it you are set.

Ravi said...

"If I were to write this text again, I would not devote the whole course to this one technique, but spend most of the time on the use of practical algorithms -- like hashing -- and on developing the right intuition on how to use them in today's large scale distributed environments that we didn't have 20 years ago."

Udi, I wish you *would* write a new edition (or a new book)! Would be wqorth its weight in gold!

I don't think there is an algorithms text out there that addresses these issues.

Anonymous said...

Well my discrete math course (call "foundations of computer science") taught induction and recursion close together time frame wise. The biggest parts of the final were induction and writing some simple functions in standard ML.

That approach certainly seemed to work for me, but I haven't thought of asking around more.