Skip to content

Book review: The Algorithm Design Manual

Steven S. Skiena's book The Algorithm Design Manual is different from all the other algorithm books I've read so far. Skiena's book makes you aware of three things:
  • Optimize the algorithm instead of the implementation
  • Choose proper data structures
  • Recognize that many problems can be reduced to well-researched standard problems
At this point I can hear you saying "Gee sp, don't all algorithm books teach you that?". Maybe they do. All decent ones at least. But Skiena's book is different. All the other algorithm books I've read so far deal with the three points I mentioned only briefly in the introductory chapters. The rest of the books present implementations of algorithms. In Skiena's book the three points are the central theme of the book. The book teaches you how to extract the relevant information from a problem, how to transform a given problem into a well-researched problem, how to select the best data structure for the job and how to really improve algorithms. Implementations of actual algorithms or data structures were omitted. Skiena's book might be the only algorithm book that doesn't present any actual algorithm code (there are a few tiny algorithms given in pseudo-code but not many). That's what makes the book so different and yet so valuable.

The 460 pages of the book are divided into two parts, Techniques (160 pages) and Resources (300 pages). Techniques is divided into 7 chapters. The first chapter is the usual first chapter you can find in most algorithm books. It introduces the concept of algorithmic efficiency, how to measure efficiency, and how the Big Oh notation works. The chapters 2 to 5 are named "Data Structures and Sorting", "Breaking Problems Down", "Graph Algorithms", and "Combinatorial Search and Heuristic Methods". Here the reader learns about all the common algorithm design strategies (Dynamic Programming, Backtracking, Simulated Annealing, ...), common data structures (everything between arrays and suffix trees), and common algorithms on data structures (Prim's Algorithm, Kruskal's Algorithm, ...).

The highlights of the Techniques part of the book are not the descriptions of the common data structures and algorithms though. The highlights are the stories the author tells about the algorithms and data structures and how they helped him to solve difficult problems in the past. There's one story - named "Mystery of the Pyramids" - which I found particularly nifty. One of the three bullet points I mentioned above says "Recognize that many problems can be reduced to well-researched standard problems". "Mystery of the Pyramids" really drove that point home for me. Once upon a time the author was approached by someone who wanted to prove some variant of Waring's problem for all integers between 1 and 1,000,000,000. Skiena recognized that the problem was a variant of the Knapsack problem and used this knowledge to design an algorithm to solve the original problem. The entire book contains about 15 stories like that and they're all very interesting.

The sixth chapter is the only theoretical chapter of the book. It's called "Intractable Problems and Approximations". When I say theoretical I don't really mean Knuth-theoretical. I mean just a bit more academic than the other chapters which are all very down-to-earth and close to what a programmer needs for his day job. This chapter is all about NP-hard problems and how to recognize them. Skiena introduces reduction, the standard way to determine whether a problem is NP-hard or not. This technique should help the reader to develop NP-hardness proofs for his own problems. Several standard reductions of various difficulties are presented and explained.

The Resources part of the book is primarily a reference of common data structures and algorithmic problems. Each data structure and algorithm is defined (input and output) and discussed on two or three pages on average. The discussion of each problem includes an explanation of the problem, possible variants that make the problem easier, suggestions on how to implement the problem, standard algorithms if available, and reference implementations if available. This part is another big strength of the book. The discussion of the variants of problems and data structures and the pros and cons of possible implementations make it a perfect reference to get a first idea about something you want to implement.

If you aren't already familiar with the book I suggest you add it to your to-read list. There's some good news too. You don't have to buy the book. It's available online in HTML form.

Trackbacks

No Trackbacks

Comments

Display comments as Linear | Threaded

Luiz Carlos B. Vessosa Jr. on :

Thank you for your book review sp!
I Always love to read it!

Cheers!

Add Comment

Enclosing asterisks marks text as bold (*word*), underscore are made via _word_.
Standard emoticons like :-) and ;-) are converted to images.
BBCode format allowed
Form options

Submitted comments will be subject to moderation before being displayed.