The usefulness of a textbook depends not so much on substance, which tends toward uniformity as a discipline matures, as on style and design. To his credit, Sedgewick makes his design decisions explicit.

This advanced survey of algorithms for undergraduates consists of 45 short chapters distributed among eight parts. Each chapter (except the first) is followed by ten exercises for which answers are, to the book’s detriment, not provided. The first part deals rapidly with primary algorithms, of the sort always covered in the data structures course. The next five parts cover sorting, searching, string processing, geometric problems, and graphs. The last two parts look at algorithms in arithmetic and numerical analysis and present a potpourri of “advanced topics” (parallel algorithms, fast Fourier transform, dynamic programming, linear programming, exhaustive search, and NP-complete problems). The bibliographies after each part contain 67 items (counting a few duplicates). The book is perhaps best suited for the fundamental algorithms course, with courses in data structures and C as prerequisites.

Textbook writers commonly underestimate the mathematical prerequisites for their books so as not to discourage prospective readers and adopters. Is Plauger [1] guilty of hyperbole when he asserts that “an amazing number of computer people are frightened of mathematics”? Sedgewick states that “little specific preparation in mathematics is required for the bulk of the book, though a certain amount of mathematical maturity is definitely helpful.” He does not explain how a student could achieve such maturity without having taken several courses in mathematics.

Algorithms have to be written in a programming language. Any choice will alienate a significant portion of an author’s potential readership (unless the choice is pseudocode or an imaginary language, which alienates everybody). Sedgewick opts for C (the second edition of a Pascal version of the current book was published in 1988), which is commendable in view of C’s increasing importance for working programmers. To provide for easy translation to other languages, however, the algorithms generally do not take advantage of peculiarly C constructs, rendering the algorithms less useful than they might otherwise have been. The author is not concerned with presenting the most efficient programs, which he characterizes as “over-optimized”; rather, he chooses the “simplest reasonable implementations of the best algorithms.” For pedagogical purposes, this decision is probably wise.

The programs contain no in-line comments. The rationale is that the programs are meant to be read “as part of the surrounding text.” This decision makes the programs harder to understand because the text must bear the entire burden of explication. The light typeface used for program lines and the tendency to cram several program statements into a single line also impede understanding.

Following the author’s exhortations to implement and experiment, I selected the first algorithm in the text, keyed it into my Turbo C editor, added a driver program, and ran it; everything worked as advertised. I encountered trouble with my second selection (p. 279), described as a brute-force algorithm to find the first occurrence of string p in string a:

int brutesearch(char *p,char *a)

{

int i, j, M = strlen(p), N = strlen(a);

for (i = 0, j = 0; j < M && i < N; i++, j++)

while (a[i] !=p[j]) {i-= j−1; j = 0; }

if (j == M) return i−M; else return i;

}

When a match exists, the program produced the expected results. When no match exists, the program is supposed to return the string length of a; in fact, it returns various values, depending on the characters in string p. The program can apparently be fixed by adding && i < N to the test in the while statement head and changing the statement after the else to return i− j.

In an ideal world, I would test each of the 162 programs listed in the program index; in fact, I ran two programs and found one defective. Because this lucidly written volume otherwise gives every evidence of being constructed with care and attention to detail, I assume that my tiny sample was unrepresentative.