The authors have brilliantly and solidly achieved their aim “to teach reasoning as well as concepts and skills,” with a breadth that characterizes the scope of today’s computing science. Although the target audience is undergraduates with knowledge of precalculus, I can say with no hesitation that experienced professionals who program computers, or otherwise need to have a basis for choice among algorithms, will gain much from a dive (to any depth) into this carefully designed book. The experienced ones will see familiar topics and algorithms from new angles, in a new light, and presented with utmost clarity.
Chapters 1 to 8, 13 to 18, and 21 to 25 form the book’s “skeleton” (the authors’ term) and are designed as a necessary basis for a plausibly complete introductory computer science (CS) course. They cover fundamental concepts (proof techniques, induction, relations and functions, countability); directed and undirected graphs (intentionally in that order); and counting. The “extra-skeletal”--but equally informative and engaging--chapters are also in piecewise contiguous blocks: 9 to 12 on logic; 19 and 20 on automata and formal languages; 26 to 29 on discrete probability; and 30 and 31 on modular arithmetic and cryptography.
The book’s philosophy is stated--accurately, as I’ve verified--at the very beginning, in the preface: “We stress the art of proof in the hope that computer scientists will learn to think formally and precisely. Almost every formula and theorem is proved in full.”
By way of thought experiment, if one were to stop reading the book at this earliest point and guess at the style and structure of the remainder, one might imagine a good but dry and formalistic enumeration and treatment of the mathematical pillars of computing. I was, on the contrary, pleasantly shocked (if that is not an oxymoron) by how inaccurate such an expectation would have been. The substance of this work is optimally organized and presented with the best pedagogy that I’ve encountered (which is saying a lot). This includes a clear and precise style of writing that eschews the esoteric without sacrifice of substance. There is no hint of “look how smart and sophisticated we, the authors, are.” The highly instructive problem sets, around ten problems per chapter, contribute to this work’s high quality, as does the page layout of placing (what would otherwise be foot) notes and figures in the vertical margins; no more tiresome eye-movements and losses of place!
Chapter 1, “The Pigeonhole Principle,” asserts what I call a manageable manifesto: “This is a book about the mathematics that is used to reason about the behavior of computer programs.” The reasoning, exercised in this and other chapters, concerns software’s abiding issues: correctness, provable run to completion, and generic, order-of-magnitude measures of execution time as function of input size. Chapter 21, “Order Notation,” on the heretofore unpleasant (to me) subject of execution time, is the clearest treatment of Big-O, Big-Omega, and Big-Theta criteria I’ve encountered.
As mentioned, instructors have license to include such optional (my word) chapters as 9 through 12, which cover propositional and predicate logic. These are ones I would invariably include in my version of an introductory course that uses this book. Aside from the characteristically precise and careful treatment, the notions of constructive and non-constructive proofs are explicated. The careful formalization of quantification logic is the best I’ve come across. Formalization, of course, enables automatic reasoning, the basis of formal methods of software construction and verification. (Formal methods are no longer only “for beekeepers and stamp collectors,” as a code inspection guru once told me in reply to my probing.)
Mathematical induction is presented both conventionally and in enrichment style. An example of the latter is the fascinating Thue sequence of bit-strings, along with a separate chapter (4) dedicated to strong induction that is admittedly “a convenience” (as the solution to Problem 4.6 would confirm). Such conveniences are most welcome to computing professionals and fellow travelers. A subsequent chapter (8) on structural induction is part of the book’s core theory.
Set theory, being by now time-honored, is also presented in a stimulating way, by way of revealing what (un)countability can mean: as computer algorithms are finite strings over finite alphabets, their set is countable; however, functions over, for example, the (uncountable) real numbers are not.
The chapters on the core topic of graph theory are a perfect distillation of this vast topic for CS; they will obviate the necessity of reading separate books on this highly relevant topic. Treating directed graphs (digraphs) first is excellent pedagogy: “The underlying structure of any discrete-state system [such as a computer] will be a digraph.” Graph coloring is also presented, and minimization of the number of registers for a computation “is a graph-coloring problem.”
In summary, the combination of content selection, clarity, economy, and genuine rigor that averts “rigor mortis” yields an outstanding book that has my highest recommendation. The oft-quoted refrain, “I wish this book had existed when I was an undergraduate,” certainly applies here.
More reviews about this item: Amazon