A classical collection

Introduction to Algorithms is truly massive. It purports to be a "comprehensive introduction to the modern study of algorithms", but in the preface the authors admit that the book is not "complete". A kind description would be "classical", a less kind one "old-fashioned". At any rate, it is very American-oriented, unsurprising given that its authors hail from Dartmouth College, the Massachusetts Institute of Technology and Columbia University.

Aimed at computer-science undergraduate and graduate courses, the book is unlikely to be used in its entirety by any one course. But this is one of its strengths. The largely self-contained chapters build from simple to more advanced material. Sections within chapters act as well-chosen break points. Thus the book is very flexible. It can also act as a reference book.

The algorithms are generally well explained, with diagrams and pseudo-code where appropriate; the explanation of the rather magical Quicksort algorithm is particularly good and accessible. A reasonable level of competence is required in recursion, simple data structures such as arrays and linked lists, and mathematical induction. Indeed, recursion is introduced too briefly and recursively: a more explicit introduction of this key topic would have been worthwhile.

A good number of exercises and problems are included, but no answers are available, apparently to avoid encouraging cheating. There is a significant bibliography (17 pages) and index (36 pages).

In revising the book for its second edition, two chapters have been deleted and three added, changes have been made to sections, and a new author has been added.

The book claims to combine "rigor and completeness". It is rigorous, but not so formal as to alienate able engineering-oriented students. It is complete in the sense that it covers all undergraduate needs for a classical computer-science education, but it omits more modern algorithms and subject areas that are generally of more interest in Europe than in the United States. For example, functional and logic programming paradigms are not mentioned, ditto lazy algorithms and unification, and genetic algorithms. The first and only mention of "parallel" in the index is for page 1,051, which refers to the last problem in the book before the appendices. All the algorithms seem implicitly to assume a conventional sequential von Neumann-style computational machine. In the second edition, one might have expected a more adventurous view of this relatively fast-moving field, or at least a mention of some of the new areas under development.

I recommend the book to the conservative teacher of computer science seeking a sound exposition of the classical sequential imperative view of computing. I am sure it will continue to do well in the US, and will also have a reasonable market in Europe and elsewhere. At least the second edition has a website for those contemplating recommending or using the book: mitpress.mit.edu/algorithms

Jonathan Bowen is professor of computing, South Bank University.