“Algorithms and Complexity”, written by Herbert S. Wilf, is one of the best introduction ever written on the subject of algorithms analysis and complexity. With a total of 219 pages including the index, it is a short book, but it almost doesn’t miss anything. Its brievity is actually one of its numerous achievements, and one that sets it aside from the rest of the litterature on this topic. It allows you to read it from cover to cover multiple times and really understand the matter while being encouraged by your quick progress. It is during my third reading that I decided to write this review.
I got a hardcover copy of the second edition, which includes solutions to most exercises that you will find at the end of each section. The difficulty level of the exercices themselves range from easy to very challenging, with some refreshing ones like “Find out when and where Euclid lived, and with exactly what words he described his algorithm”.
The first edition, without solutions to exercises, is available to download free of charge. The content between the first and second edition hasn’t changed significantly. Although I have lately tried to avoid getting hard copies of books (for lack of room on my shelves), I must say that this edition looks very solid and is very pleasant to read.
The book starts with an interesting short introduction that really gives you a bird’s eye view of what the book is about. Hopefully, it will peak your curiosity as it peaked mine. Not that anything ground breaking or mysterious is presented in these couple of pages, but the way the subject of algorithmic complexity exposed was definitely unique to me. It’s also your first chance to appreciate the very precise, concise yet humorous style of its author.
“Recursive Algorithms”, the second chapter, despite its first section, should not be mistaken for an introduction to recursion. If you’re looking for that, one of my favorites can be found in Steven S. Skiena’s “The algorithm design manual”. Most of this chapter’s content is actually about the analysis of some important and typical recursive algorithms, like quicksort.
It shows the systematic and methodological approach that will be used by the author throughout the book. First, a relatively naive algorithm capable of solving a given problem is presented using pseudo-code and prose. Then, it is analyzed and its weaknesses in terms of complexity are discussed. Next, a more advanced algorithm solving the same problem but with better characteristics regarding complexity is presented, and the process repeats for a few iterations. I find this incremental approach to be great to grasp complex problems gradually.
For each algorithm presented, mathematical proofs are given every time the author make an important claim about their properties. While it can be a bit unusual at first for a reader not used to mathematical litterature, it turns out to be very empowering because it tells you why these important claims about algorithms can be made with confidence.
The chapter about network flows follows the same pattern. However, because the algorithms presented are a bit more complex, proofs and pseudo-code can become harder to follow in the absence of diagrams. This is to me the only shortcoming of this book. Don’t worry though, it won’t prevent you from enjoying the excellent selection of algorithms and their brilliant analysis.
Finally, the last chapter about NP-completeness is another breakthrough of this work. Each of the concepts that are necessary to grasp what NP-completeness are presented carefully, one step at a time. You can really get why the class of NP-complete problems is really important. As usual, this chapter is supported by proofs and a very rigourous method, while maintaining an entertaining tone.
I can’t recommend this book enough. It is special in many ways, and I think that anyone interested in algorithms should get it and read it several times.Julien Gilli 09 June 2013