cokasaki@PROOF.ERGO.CS.CMU.EDU (Chris Okasaki) (03/16/90)
I just finished re-reading a wonderful article from the November '88 CACM on the use of proof techniques developed in mathematical settings (namely, various kinds of induction) in algorithm design. The article was titled "Using Induction to Design Algorithm" and was written by Udi Manber. In the article, Manber refers to a textbook that he had written based on the same approach. (The textbook is called "Introduction to Algorithms--A Creative Approach" and was to have been published in 1989). Two requests: First, I'd appreciate information or comments from anyone who has actually seen the book. Second, I'd be interested in hearing if anyone has actually tried to use Manber's approach in the classroom. The analogy between induction and algorithm design seems like a particularly powerful one, but only for students with a sufficiently advanced mathematical background. I'm not sure how well it would work in practice. Thanks, Chris cokasaki@proof.ergo.cs.cmu.edu