This book should be on any short list for a central course in computer science. It is designed to provide a uniform background on which all students might draw. It has a good-humored, easy style, which would make any reader unwilling to close the book after opening it anywhere. All computer scientists should have this book.

The key to its centrality is the authors’ desire to skip technical details. Older readers will remember when algorithms were largely for integer factorizations and for the solution of differential equations. These uses stimulated diverse objectives such as logarithmic searches for factors and memory management for matrices. Algorithmics have more abstract uses today, such as screen management and combinatorics. The authors use domino and tiling problems to develop insight and intuition.

The book has several parts. Parts 1 and 2 provide a background possibly familiar to most students. Part 3, “Limitations and Robustness,” is the core of the text and must be learned (or relearned). Part 4, “Relaxing the Rules,” and Part 5, “The Bigger Picture,” come closer to the cutting edge and current realities. These parts will need continuous revision, for example, as quantum computing becomes a reality (the current description is not too helpful).

Part 3, the core, is devoted to Turing. It features the inability to find an algorithm that can decide what another algorithm will do before running it (the halting problem), or one that can tell if it is “talking to a machine or a human.” A plethora of Bible quotations (mostly irrelevant) seem to make Turing messianic (or perhaps they are just “good clean fun”). It is truly surprising that no reference is made to Bertrand Russell, whose well-established treatment of paradoxes is so analogous to noncomputability. (Paradoxes result essentially from self-reference in a set of objects.)

Incidentally, the bibliography is organized in a convenient chapter-by-chapter form, which makes the book useful for advanced work, and the exercises will help instructors identify capable students.