Supplemental Material for Baldwin and Scragg, Algorithms and Data Structures: The Science of Computing; Charles River Media, 2004 (Now published by Cengage Learning)
Each of chapters 2, 3, and 4 of Algorithms and Data Structures: The Science of Computing delves into one of computer science’s methods of inquiry by exploring some element of that method in detail. In chapter 3, the general method is theoretical analysis, and the specific element is proof. The critical lesson of this chapter is that it is possible to reason rigorously and logically about the properties of algorithms.
While chapters 2, 3, and 4 nominally place each method of inquiry into its own chapter, they also illustrate that the methods are not really as easily separable as this organization suggests. For example, many of the formal ideas in chapter 3 grow from chapter 2’s discussion of preconditions and postconditions; one of these lines of development leads to the idea of class invariants. Rather than leave class invariants as a purely formal notion related to correctness, however, chapter 3 uses them to explain why classes need constructors — expanding issues of class and algorithm design explored in chapter 2. Chapter 3 ends by introducing theoretical performance analysis, which leads to a need to compare theoretical predictions to observable behavior that in turn motivates chapter 4’s presentation of experimentation.
The inseparability of computer science’s methods of inquiry is a theme that should pervade courses based on Algorithms and Data Structures: The Science of Computing. Students should finish such courses (and readers should finish the book) appreciating that even if they most enjoy one method (e.g., some enjoy crafting programs, others enjoy proving theorems), they will be more successful in that method if they can also understand and use the others.
I find that resource analyses (e.g., counting the number of steps an algorithm executes) make good examples to use in lectures about chapter 3. Although this chapter concentrates on correctness, mentioning resource analysis only at the end, the reasoning used in resource analysis is similar to that used elsewhere in the chapter. While an instructor should certainly make time to answer any questions students have about correctness, simple resource analyses neatly supplement the chapter’s focus on correctness, and are comprehensible to students. I find that students can do informal counts of the steps executed by simple loops (e.g., determine how many messages a “for” loop sends while moving one of chapter 2’s robots n tiles), and that they can follow more complicated analyses (e.g., quadratic-time loops) with some effort. Furthermore, ending discussion of this chapter with a theoretical analysis whose result can be tested by a short experiment makes a particularly smooth transition to chapter 4.
Copyright © 2005 Charles River Media. All rights reserved.
Revised Aug. 9, 2005 by Doug Baldwin