Supplemental Material for Baldwin and Scragg, Algorithms and Data Structures: The Science of Computing; Charles River Media, 2004 (Now published by Cengage Learning)
This chapter provides some important definitions (e.g., of “problem,” “algorithm,” each of the three methods of inquiry), but can be covered quickly in a course. In fact, the authors usually present the material in this chapter verbally in the introductory class meeting, without assigning students to actually read the chapter. Alternatively, if there isn’t time to cover this material in the first class meeting, it can be done in the second, with students reading the chapter before that meeting.
In the classroom, we like to develop this chapter’s central ideas via an example, similar in spirit to the beverage-chilling example in the text. The example problem and one or more algorithms to solve it illustrate the concepts of “problem” and “algorithm.” Explaining the thinking that leads to the algorithm(s) illustrates design, brief arguments for the correctness or speed of the algorithm(s) illustrates theoretical reasoning, and comparing the theoretical conclusions to a demonstration of the algorithm illustrates empirical analysis. At this point in a course, the theoretical arguments can be informal rather than mathematical, and “demonstrations” of an algorithm can involve a person, rather than a program, carrying out the algorithm. A suitable example can probably be presented in about half an hour of pure lecture. However, the lesson will be more effective if it uses more time in order to involve students in developing algorithms, suggesting parts of the theoretical analysis, or participating in the empirical demonstration.
A fun example, although one that requires having the right equipment, is using a balance scale to find one heavy coin in a large set of otherwise identical coins. This problem can be solved by either sequential search (put single coins on each side of the balance until one is heavier than the other), or binary search (balance halves of the set against each other, repeating with the heavy half, until only one coin is left). Both algorithms can actually be demonstrated with United States coinage: In 1982 the United States changed the penny from a mostly copper alloy to copper-plated zinc; to a person, the plated pennies look and feel the same as the solid ones, but in fact they are slightly lighter. A sensitive, but not unreasonably delicate, balance can detect this difference. We once found a university chemistry department discarding as surplus a balance sensitive enough to binary search for one heavy penny in a set of 128; instructors who aren’t so fortunate may be able to borrow a balance from a chemistry or physics department. Regardless of where the balance comes from, however, using it in a coin-finding algorithm requires familiarity with the balance and concentration on the algorithm — it is an extremely good idea to make several practice runs before any public demonstration!
Another example, which requires less equipment than finding heavy coins, is finding a “special” card, coin, marble, or similar item in a set by asking yes/no questions about items or subsets of items. This problem can also be solved by a sequential (ask about single items) or binary (ask if the special item is in a subset containing half the items) search. It is naturally posed as a game between one player (or team), who selects the special item and answers questions, and another, who asks the questions. The asker’s goal in this game is to ask the fewest questions before finding the special item, while the answerer tries to make the number of questions as large as possible. When we use this example, the instructor is the answerer and the students are a team of askers. The answerer can force the asker to ask the maximum number of questions by not actually selecting a special item until a question chooses between two items, one of which must be special; all other questions should be answered in a way that puts the special item in the largest possible subset of the items (making each answer consistent with prior ones, of course). Notice that this is the adversary strategy described in chapter 16’s optimality arguments about searching. Using it ensures that algorithms will always have their worst-case performance, making performance predictable between demonstrations, and simplifying comparisons of algorithms.
Copyright © 2004 Charles River Media. All rights reserved.
Revised Aug. 9, 2005 by Doug Baldwin