Supplemental Material for Baldwin and Scragg, Algorithms and Data Structures: The Science of Computing; Charles River Media, 2004 (Now published by Cengage Learning)
These notes discuss the laboratory exercise entitled “Induction and Recursive Algorithms”.
This lab nominally helps students learn both to design recursive algorithms and to use induction to prove recursive algorithms correct. But it is significant that the lab asks students to do those two things (nearly) simultaneously. In that manner, we hope to help students appreciate how design and correctness proofs work hand in hand with each other: reasoning about correctness helps one design an algorithm, and the proof usually reflects the design very closely.
We deliberately chose the problems in this lab to be in some way hard for students. The recursions have subtle boundary conditions, the problem domains are likely to be a little bit foreign to students, etc. This means that students should be unlikely to intuitively see an “obviously” correct algorithm for any problem, which in turn should help students appreciate the value of the formal correctness proofs.
Variations on this lab can be created by substituting problems from the “Elementary Recursion” or “Intermediate Recursion” labs for any of the original problems (or adding problems from those labs alongside the originals). While the problems from the recursion labs are a little easier than the ones in this lab, that fact could make them good warm-up exercises. Problems can either be ones the instructor left out when students did the recursion labs, or students can be asked to go back and prove correct algorithms that they designed in an earlier lab session.
To reinforce the lessons of this lab, instructors should encourage students to use informal induction proofs as debugging aids for recursive algorithms in future exercises. For example, ask students to check that their base case is correct, ask them to check recursive cases by assuming that recursive messages work correctly and seeing if the recursive case should produce the right result under that assumption, ask them to verify that the parameters to recursive messages correspond to plausible induction hypotheses, etc.
Copyright © 2004 Charles River Media. All rights reserved.
Revised Aug. 9, 2005 by Doug Baldwin