Author: George Heineman, Gary Pollice, Stanley Selkow
Audience: Programmers wanting to catch up on algorithms
Reviewer: Mike James
Over the festive season IProgrammer asks its reviewers to recommend books that are worth a second look in case you missed them. Mike James nominated one of the most enjoyable books on algorithms.
In my opinion this second edition is an improvement on an already very good book and raised the question, can it get any better?
There are lots of algorithm books, but this one is a little different. A standard algorithm book simply presents common or classic algorithms to do a range of things in the language of choice. Some of them, like Donald Knuth’s classic, “The Art of Computer Programming”, indulge in detailed mathematical analysis of the efficiency and properties of the algorithms. This book, however, isn’t at all academic and it’s a very good and easy read. If you are looking for a deep analysis and encyclopedic coverage then you probably do need The Art of Computer Programming or Introduction to Algorithms, 3rd Ed.
Returning to Algorithms in a Nutshell, the preface states that the second edition has tried to stay true to the aims of the first:
- To use real code not pseudo-code.
- Separate the algorithm from the problem
- Introduce just enough math
- Support mathematical analysis empirically.
The language used is C except for the small number of new algorithms introduced where Python is used. This use of two languages is a little strange but not a huge problem.
The first chapter presents a case study describing how, despite the best intentions of the programmers concerned, selecting an algorithm for a particular job is difficult. The account is interesting and well told, a sort of “who dun-it” and it doesn’t matter that it's obvious that it was the algorithm that did it. Following this there is an introduction to the ideas involved in evaluating and understanding algorithms. Even if you know about “big O” notation it makes a good refresher course.
From here we launch into a consideration of algorithms by type with searching and sorting being the obvious place to start. Each algorithm is placed into its context and an explanation of how it works is given.
What is important to emphasis is that while the book presents the properties of the algorithms without trying to oversimplify you are not subjected to long derivations of the execution times or space requirements. The whole presentation is informal but informative at just the right level for a working programmer.
Moving on from the essential skills of searching and sorting the following chapters are more varied and less universally useful: Graph algorithms (e.g. shortest path), Path finding in AI (e.g. Minimax, Alphabeta pruning), Network flow (e.g. Max flow, Linear Programming) and Computational Geometry (Convex Hull, Nearest Neighbour). Clearly which algorithms are of interest depends on what you are working on but the selection covers a useful range and you can expect to encounter them all in a reasonable programming career.
The final part of the book deals with slightly more exotic topics such as what to do when you can’t get find a suitable algorithm – including go parallel and try randomised algorithms. The Epilogue ends the book with a collection of principles that you should apply to your interaction with algorithms. Take to heart:
Writing Algorithms Is Hard – Testing Algorithms is Harder
If you have the first edition then it is worth mentioning that there is an additional chapter, Chapter 10: Spatial Algorithms, which includes R trees, and Quadtrees.
Four other algorithms have also been added:
- Fortune's algorithm (for computing Voronoi diagrams)
- Merge sort
- Multithreaded Quicksort
- AVL Balanced Binary Trees
Despite not covering much of the academic analysis needed for a computer science course, this would make a really good basis for such a course or background reading.
This book is a “keeper” - make room for it on your bookshelf as it’s essential reading and great for making up for what you never learned in Computer Science lectures.
The Art of Computer Programming, Volume 4, Fascicle 1 Rated 5
Introduction to Algorithms Rated 5
Algorithms Unlocked Rated 4