All serious programmers and computer scientists probably have at least a couple of algorithm books sitting on their bookshelves (or, perhaps, algorithms Web pages in their bookmarks). There are, of course, lots to choose from, some focusing on specific kinds of algorithms (graph algorithms, numerical algorithms, randomized algorithms), some focusing on different environments (sequential, parallel), and some focusing on specific languages (C, Java).

So why write yet another book on algorithms? Because this one is indeed a bit different. It does present a couple of standard algorithms, algorithms that would be familiar from most other books on the subject, and does the same kind of big O analysis, but it goes an important step further, by talking about, and presenting in about as lucid a way as possible, some of the seamier sides of things.

While the title of the book mentions “algorithm analysis,” the bulk of the book is actually about programs, which the author describes (more or less) as actual implementations of algorithms. He then considers some of the things that can go wrong with a specific algorithm, even with a correct translation of the algorithm into a specific programming language and environment.

This is where the book really shines, with a number of very good examples of how things like the hardware memory hierarchy (especially virtual memory), exception handling, and the like can make an algorithm with good behavior into a program that behaves very badly indeed. One of the first of these (and probably the easiest to understand) is how badly the following simple code can misbehave for large enough arrays A, B, C:

for i := 1 to n do

   for j := 1 to n do

      B[i,j] = A[i,j] + B[i,j]

Changing the order in which the loops are nested can change the runtime of this tiny fragment by several (even many) orders of magnitude. Worse yet, the same fragment might behave well with one language and worse with another (depending on how the language stores multidimensional arrays). In a related example, a detailed examination of a loop involving several operations on arrays reveals not only how it might behave poorly, but also how to restructure the loop (into several loops) to eliminate many possible secondary memory accesses.

In another section, asymptotic complexities of algorithms are considered. The effect of constants on the dominating term is analyzed to show that big O analysis is incomplete when it comes to real programs, and that what you knew about which algorithm is best might well be wrong.

Other topics include floating point inaccuracies, the influence different parameter passing mechanisms can have, and even a quick glance at infeasibility and where it might arise in practice.

The author notes that many programmers see algorithm analysis as a waste of time, and claims that “algorithm analysis has much to offer to programmers, provided they know how to use it.” He backs up this claim with good examples, and makes this a worthwhile read, especially for the dubious. On the other hand, the book does have a few problems (only a couple of which will be mentioned here).

One persistent problem is the quantity and readability of the footnotes. There are many footnotes, perhaps averaging one per page, and these are often relatively long. Since they are printed in small type, any mathematical formulas are usually seriously compressed for space reasons, making them even less readable than usual. Worse yet, in the main text there are some footnote numbers planted firmly in the middle of formulas. More than once, these led me to wonder where that strange exponent came from. Removing these would lessen the value of the book, but, in their current state, they are frequently difficult to read. Perhaps printing footnotes on facing pages might help.

In a discussion of parameter passing, an example of multiplying a matrix by itself and putting the result into the original is given, and it is noted that this will usually produce an incorrect answer, since it overwrites the matrix as it does the computation. An alternate formulation of the multiplication is given, but with the cost of allocating a temporary matrix and copying the result back. This is not required, however, unless the resulting matrix is one of the inputs, and would generally be a wasteful cost. This is a general problem (aliasing), and would have been worth mentioning.

These problems (as well as a number of other minor problems) do not seriously detract from the value of this book, but addressing them would make this book all the more valuable. Even as it stands, the book is highly recommended reading for students of programming or software engineering, and for practitioners who feel the analysis of algorithms has nothing to offer them. If these few problems were resolved, this book would be a very valuable addition to any serious programmer’s bookshelf.