This is a review of John MacCormick's book from Princeton University Press, 9 Algorithms That Changed the Future.
I really like this book. It gives clear, very high level explanations of some common algorithms, with a special focus on those that make common web tasks work (e.g., Google PageRank, Database operations, public-key encryption, etc). The style of language employed is plain and straightforward, allowing the author to make some difficult topics accessible to those without a strong background in math or computer science. The explanations are most often accomplished through the use of some cleverly crafted metaphors and analogies. The best example is the section on public key encryption, which uses an analogy of mixing paint. It is conceptually sublime, and in contrast to some of the other chapters, does not give short shrift to the mathematics involved. In each of the nine algorithms discussed, MacCormick provides enough background discussion to place the idea in context, but does not overwhelm the reader with a torrent of unfamiliar characters, terms, and concepts. The book has a consistent tone and approach throughout, though the section on databases is a bit slow and opaque when compared to the others. The first few chapters are truly excellent, though my favorite chapter is unquestionably the one on undecidability. First and foremost, it is about the ideas of Alan Turing, a personal hero of mine (and many lovers of computer science). Secondly, it explains a complicated idea so simply and beautifully. Like most good non-fiction, it also forces one to ask some very interesting follow up questions. It absolutely has made me want to learn more about decidability, and how it relates to other problems in mathematics and computer science. Overall, this is an excellent conceptual introduction to some important algorithms and I recommend it highly for anyone with an interest in the subject.
My main point of contention here is about word choice. While the author makes it clear in the introduction that he is writing the book for laypersons, I must take issue with how he refers to all of the important concepts in the book. Namely, everything is a 'trick' (e.g., the metaword trick, the checksum trick, etc.) This naming scheme certainly makes some complicated ideas less intimidating, but it also seems overly cutesy and might undermine the purported purpose of his book. For example, the word "trick" could be taken to mean that algorithmic ideas are some sort of inaccessible magic, something that a few dark wizards are able to conjure up from a realm beyond the reach of normal humans. I don't like it. This dissatisfaction is mitigated somewhat by the author's introduction, which supplies his definition of tricks: "clever techniques for accomplishing goals that would otherwise be difficult or impossible". Unfortunately, this definition was easily forgotten as I read, and in effect it did little to ease my qualms about the constant use of the term. Perhaps my connotation of the word is different from the author's. At any rate, this is a small gripe about an otherwise great book. For the mathematically inclined or those with some previous experience with these ideas, you might feel unsatisfied with the lack of math in some of the explanations. I completely understand the author's motivation for the simplification/omission of some beautiful maths, but it left me with a nagging feeling of unconsummated intellectual anticipation (perhaps this is a feature, not a bug - after all, the book left me wanting more!). To his credit, MacCormick supplies ample crossreferences to other materials that give a more rigorous treatment to these ideas.
The potential instructional impact of this book is quite high. As a first introduction to some of the ideas that make modern computers and the internet possible, this book could be a valuable resource, even (perhaps especially) at the high-school level. One of the author's stated goals is to give the reader a "true appreciation of the most ubiquitous, inscrutable black box of our time: the personal computer." For the most part, this is exactly what the author has accomplished. To me, one of the most empowering things about studying computer science is the sense of peeking behind the curtain that shrouds some powerful force (like Google search) and coming to understand, at least on some rudimentary level, exactly what happens when a human user interacts with that force. It makes you feel like you are the possessor of some great secret, and it's great fun. In this way, an understanding of computer science, like all great sciences, can paradoxically inspire awe by removing the mystery of something. As a student, there is no greater feeling. In MacCormick's book, I think the plain explanations, especially of things like PageRank and public key encryption, could help secondary students get to that point, perhaps in the context of an introductory CS class (CS Principles, maybe?). Going forward, I may try to use portions of it as an introduction to algorithms in some high school classes. Finally, I think the section on decidability gives a great high-level introduction to the philosophy of proof. As someone who has recently taught a classical geometry course, it seemed to me that MacCormick was making a convincing argument for the continued use of the much reviled two-column proof. At any rate, he provides an explanation of what proof is from a mathematical standpoint. Here is my favorite line:
"As long as you accept the basic axioms of mathematics (such as 1+1=2), the chain of deductive reasoning used by mathematicians results in absolute certainty that various other statements are true..."
It seems to me that the major unstated goal of classical geometry courses is to help students understand this point.
I read this book at the same time as I read a book on the traveling salesman problem, so I found a lot of connections to that topic. The section on undecidability also provided other areas for exploration. Here are a few ideas and questions that I took away from my reading.