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!

17 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 Antolín Camarena 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.

Airik 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.

asni singh said...

Get Started to activate office setup by visiting office website and enter office product key to verify it.If you already entered a product key and looking for your software, go to office.com/setup directly and click on my account page for office installation and manage your subscription.If you have not entered office product key yet, Follow steps for setup. Do not worry we will help you.

www.office.com/setup

asni singh said...

Garmin Express gives you the notifications as soon as the updates are available for your Garmin device. You can also sync with the Garmin connect by using the Garmin Express. Garmin Express helps you to transfer or upload your daily activities and data to your Garmin Connect account.

garmin.com/express

asni singh said...

Microsoft Office includes a wide range of desktop applications such as Word, Excel, Access, PowerPoint, Groove, OneNote, Publisher and Outlook which helps you to complete the various task easily such as writing a letter, sending an email and creating PowerPoint presentation.

office.com/setup

asni singh said...

McAfee Installation is such an easy or simple process as you have to make sure that above-mentioned prerequisites should be fulfilled before getting started with the McAfee Activation Process.

mcafee.com/activate

asni singh said...

Get Started to activate office setup by visiting office website and enter office product key to verify it.If you already entered a product key and looking for your software, go to office.com/setup directly and click on my account page for office installation and manage your subscription.If you have not entered office product key yet, Follow steps for setup. Do not worry we will help you.
www.office.com/setup

asni singh said...

Garmin Express gives you the notifications as soon as the updates are available for your Garmin device. You can also sync with the Garmin connect by using the Garmin Express. Garmin Express helps you to transfer or upload your daily activities and data to your Garmin Connect account.

garmin.com/express

asni singh said...

Microsoft Office includes a wide range of desktop applications such as Word, Excel, Access, PowerPoint, Groove, OneNote, Publisher and Outlook which helps you to complete the various task easily such as writing a letter, sending an email and creating PowerPoint presentation.

office.com/setup

asni singh said...

McAfee Installation is such an easy or simple process as you have to make sure that above-mentioned prerequisites should be fulfilled before getting started with the McAfee Activation Process.

mcafee.com/activate

Garmin Express said...

Garmin express provide free map updates are available and if you want to download free map updates for Garmin GPS, then our expert team explain tell everything about Garmin Express.

asni singh said...

McAfee.com/activate – We use our computers and smart device for almost every daily chore. This leads to the increase in cybercrime as the
cybercriminals know what people are doing on their computers. You need an effective security for your system that does not hinder with your job but also protect you from all kind of online threats.

mcafee.com/activate