Review of "The Algorithm Design Manual"

The Algorithm Design Manual, by Steven Skiena. ISBN 0-387-94860-0.

There are many good general books on algorithms -- my particular favourite is the one by Cormen, Leiserson & Rivest -- but Skiena's is unlike any other I've read. It contains few proofs, few detailed time analyses, in short little mathematical rigour; but it has a wealth of practical and heuristic advice on selecting and designing algorithms. There's lots of the sort of hand-wavy material that you'd get from a casual conversation with an expert but rarely find in textbooks. Lest it seem that I'm damning with faint, and mixed, praise, I'll be more explicit: This is a good thing, and I like it very much. But I do have a couple of faint damns: see below.

The book is in two parts. The first is a short tour (170 pages) of the world of algorithms and some useful techniques, punctuated by "war stories" about the author's practical experience. If this part of the book were intended to be a general-purpose algorithms text, it would be lamentably deficient: lots of things are missing. But it isn't.

The second part is a catalogue of useful data structures and algorithms, and of problems for which they might be useful. Almost everything is discussed very shallowly (would you believe less than two pages on hash tables and balanced trees combined?), but again that isn't the point.

So what is the point? The key difference between this and a more conventional algorithms textbook, I think, is that Skiena assumes -- as is typically true, in fact -- that if you need one of the "standard" data structures or algorithms, the ones that occupy most of a book like CL&R, then you're not actually going to implement it yourself; you're going to find someone else's implementation and use that. So what you need to know is (1) how to select standard algorithms and data structures when they're what you need, and (2) how to go about using the ideas behind them to make up something of your own when necessary. Put differently, this is a book for algorithmic engineers rather than for algorithmic scientists. (It's customary for scientists to look down their noses at engineers, but this is a serious mistake.)

You really wouldn't want this to be your only algorithms book. It doesn't have enough in it, it doesn't go deeply enough into anything, and a certain amount of the bracing mathematical rigour that the book so conspicuously lacks is ... well, good for the soul, I suppose. So go buy Cormen, Leiserson & Rivest. Then, unless you're already an expert algorist, buy this one too. If you are already an expert algorist, you probably don't need this, but it's fun to read and you might learn a thing or two anyway.

I saw a couple of recommendations that seem seriously unwise. Here's one: Skiena says that if you need to implement your own random number generator you should use a linear congruential generator, and recommends a particular one with modulus 714025. And he implies that it's safe to take a number of samples equal to the period of your RNG. This is very bad advice. It's somewhat explained, but not excused, by the fact that Skiena used the first edition of "Numerical Recipes" as a source. (The second edition was published several years before this book, and its treatment of random number generation is very much less bad.)

Another: there's a (short) section on matrix multiplication, which says that the straightforward nested-loop implementation is "tough to beat in practice". Er, no, not on machines with typical present-day (2006) memory hierarchies. Skiena discusses Strassen's O(n2.81) algorithm and the possibility of optimizing the order of operations for long chains of matrix multiplications, but says nary a word about the single issue that dominates practical linear algebra implementations.

I mentioned "Numerical Recipes" a couple of paragraphs back, and one way to summarize the good and bad points of this book is to say that it's rather like a "Numerical Recipes" for algorithms and data structures: clearly written, enjoyable, containing many useful informal tips, not very rigorous, and not always correct. But that wouldn't be quite fair, because the errors -- at least the ones I've found -- are in matters peripheral to the main thrust of the book. After all, Skiena (unlike Press et al) is by profession an expert in the main subject matter of his book.

The book comes with a CD-ROM including the complete text of the book, a pile of source code, and 30 hours of audio lectures. It has lots of exercises, mostly good and mostly quite easy. The layout is good and the quality of paper and binding seem just fine. The writing style is informal and clear. The diagrams range from adequate to excellent.