Search in Book Reviews

I am choosing to review these books together because I want to focus on the differences between the C and C++ versions. If you know anything about the standard programming reference books you will know that Robert Sedgewick's works are among the industry standard ones and with good reason. Before I go on, I should mention thatNumerical Recipes in (language of your choice) andThe Art of Computer Programmingare two of the other works that share this status in the field of Algorithms. The former has, to my mind, draconian copyright restrictions as well as some poor quality source code (suffers too much from machine conversion from the original Fortran source). The latter has a major drawback in that it remains unfinished, and one of the missing volumes is that covering graphs (do not confuse this with graphics).

Parts 1-4 of the Sedgewick books are published as a single volume for each language. Part 5 is a separate volume in each case and focuses on graph algorithms (not that if you are interested in these, you might also like to look at the recently publishedBoost Graph Libraryby Siek, Lee and Lumsdaine, as well as the source code found at www.boost.org)

The first thing I did was to start comparing the contents of the C and C++ versions of part 5. I turned to the index to see how great a difference there was in pagination and came across my first surprise, the indexes did not match. The differences are curious at first sight (at least for this reviewer). Why has program 22.3 been indexed as a sub-list of 'Adjacency-lists' in the C book but not in the C++ one? I have no idea, but clearly the indexes have been separately compiled and cannot be used to identifydifferences between the books. However having noted this difference I have both books open at their respective implementations of program 22.3 - Augmenting-paths maxflow implementation. Now we come across the fact that programs 22.1 and 22.2 are not the same for the two books. Looking carefully at these effectively answers my question, yes Sedgewick has not only Christopher Van Wyk as a consultant on C++ source code but has carefully restructured the code to meet the strengths and weaknesses of each language. This is something that I had hoped for. The book is not simply similar text with different implementation code but revised text to present appropriate code for the language used.

In the C book you will find use of static data and functions coupled to #define to provide C-style ADTs but in the C++ volume you will use of classes and templates to achieve similar objectives. And yes, in case you are wondering, the code does use some STL containers and algorithms (including some uses of the infamous vectorbool specialization). However this is a change from the code for Parts 1-4 where the author used his own containers. For consistency where stacks and queues are needed Part 5 uses the versions provided by the earlier material. I think this is unfortunate though it was probably not an easy decision to make. It is interesting to note that it was not till this book that the author (with his C++ collaborator) moved to using initialization lists for constructors. The source code is above average but probably needs more development if it were to become industrial strength code.

Both books (the part 5 volumes) provide in depth and up to date (as far as I can tell) coverage of the topic of graph algorithms. The provided source code both provides a firm foundation for full implementations and works well with the text to help the reader understand the subject. While it would be possible to use either book on a piecemeal basis I think it would be more sensible to actually work through the text once before putting it on your reference shelf. Many programmers these days seem to think that all they need is to study the syntax of their chosen language. Some understand that getting to grips with the semantics is essential. However the professional programmer (rather than the overpaid amateur) knows that a solid grounding in algorithms is essential. Studying the works of such people as Sedgewick is a good way to achieve this. Knowing where to look something up is a step in the right direction, knowing what to look up is a pre-requisite.

In conclusion, either of these books is excellent for those studying graph algorithms. The first volumes are also first class texts on the topics they cover though, in my opinion, the C++ one could do with a fourth edition to bring it in line with modern C++ programming idioms. You should choose the version appropriate to your language of choice (I note that the author is promising a version for Java). There are copious exercises and thorough coverage of the material. Now when do we get parts 6-8? Perhaps the author has been imbued with his mentor's tardiness (for those that do not know, Sedgewick studied for his Ph. D. at Stanford University under Donald Knuth).