The Algorithm Design ManualI recently found myself wanting to brush up on my algorithms background. Lots of reasons. Interviews, for one (Google set the pattern for theoretical technical interviews and a number of companies (and not all started by Google alumni) have started to follow the pattern.) Moreover, in the web world of today, and with the compute resources we have available now, I find that algorithm issues that might perhaps have been of limited relevance a few years ago are front and center. More and more of my software deals with tens of thousands of elements and has to perform "interesting" graph computations.

My goal wasn't so much to be able to whip out proofs at a moment's notice but to reinforce my intuition regarding the complexity and most applicable approaches to the problems I encounter in day-to-day work.

Now, it's not like there aren't plenty of algorithms books out there. Cormen, Leiserson, Rivest, and Stein (CLRS) is for many the gold standard. It's the text for many algorithms courses. I have a copy. But as a review resource or as reference for a tricky algorithm you need for your Facebook-killer (or maybe just killer Facebook app), it's not necessarily the best fit. It emphasizes theory (read: proofs) and often doesn't provide a lot of context that can be useful in determining the relevance of individual algorithms to different classes of problems. And it's notoriously dense. This can be mitigated in the context of an instructor-led course, but is more difficult to work around in self-study/reference.

The Algorithm Design Manual, 2nd ed, (ADM2) by Steve Skiena is a different kind of algorithms book, written in a different style. Skiena, a prof at SUNY Stony Brook, consciously omits theorems and minimizes proofs, emphasizing in their stead discussion of how to match algorithms with the applications a developer might encounter and how to understand how the differences between various approaches relate to sometimes subtle differences in real world problems. The book also emphasizes algorithm implementations, providing references to downloadable code and including a discussion of the impact of both algorithmic differences and coding issues.

The style of ADM2 is more informal than typical theoretical books, with a healthy dose of levity thrown in. The result, while not exactly easy, is definitely more approachable than more theoretical texts. This isn't too surprising, given that among Skiena's achievements is the IEEE Computer Science and Engineering Undergraduate Teaching Award.

In many cases, Skiena traces the process of the development of an algorithm rather than presenting each as a fait accompli. The extreme case of this are his "war stories", anecdotes from his own work, showing not only the process of approaching real life problems, but also the false starts that occurred along the way.

The first edition of the book came with a CD but that's been eliminated. All the material formerly on the CD is available on the book's website, www.algorist.com. The website provides summaries of many of the algorithms presented in the book with live links to references and code, as well as links to course materials from Skiena's lectures at Stony Brook. These are valuable additions to the text itself. When I found an area or two where I wasn't comfortable that I had developed a solid intuition for the material covered, going to the website and looking up the relevant lectures helped fill in the missing pieces.

The book is in two parts. The first part is typical tutorial material, but, as mentioned above, focuses on understanding of the nature, dynamics, and applicability of the algorithms presented. The second half of the book is a catalog of problems and algorithmic solutions, grouped by class, e.g., graph algorithms, string algorithms, etc. I found the parts complementary and equally useful. Not only did I want to review the fundamental data structures and algorithms, but also to develop a better intuition about the classes of problems and solutions. This is something one gets through experience if one is immersed in theory and algorithms on a daily basis, but I personally find harder to come by since it is only one component of my work. I found the discussions in the catalog, which I admit to reading cover to cover, particularly useful in this regard.

What you won't find in ADM2 (it's actually a significantly smaller book than CLRS) is an emphasis on and demonstration of proof techniques and detailed analysis of every possible variant of an algorithm. It assumes some background in data structures. It provides most of the discrete math necessary to understand the dynamics of algorithms but the more comfortable with discrete math the reader is, the more useful that material may be, since the background in ADM2 is brief, more at a review level. (Skiena's discrete math lectures are also available via his Stony Brook website.) ADM2 does not cover probabilistic analysis.

Overall, for me ADM2 succeeded in being a concrete review of classes of algorithms and classes of applications those algorithms solve. It won't replace my copy of CLRS, but complements it well. It's the first book I turn to, going to other books and references in those cases where I need more depth. And when I do need more depth, it provides the background necesasry to understand the more terse/dense theoretical references.