Rarely do popularizations enable the reader the grasp the essence of the concepts presented. The choice is often between two extremes. At one end, some authors offer a simplification that includes anecdotes with statements about the ideas. At the other, authors offer an explanation that gives more of the flavor but uses technical details that make it inaccessible to many readers. This one is an exception.
MacCormick states in the conclusion that he initially thought that he would only be able to give non-technical insights for about half of the algorithms presented, but was pleasantly surprised that he could explain them all in a meaningful way without discussing the obscuring prerequisites. Readers will be pleasantly surprised as well, because he masterfully uses everyday analogies in a way that gets to the heart of the ideas (he calls them tricks) that make the algorithms work. While this is essential for readers without mathematical background, the other lesson that jumps out is that this is a great way to introduce these algorithms to mathematics and computer science students who will go on to more in-depth treatments. Getting the big picture is a memory aid and organizing tool for what may otherwise be just a bunch of derivations.
One could make a case for many algorithms related to computers and computing that “changed the future.” The four criteria used in this book are that the algorithm is:
- used by ordinary computer users, like a search but unlike a compiler.
- applied to a specific problem, unlike generic sorting algorithms.
- related to the theory of computer science. (This is to counter the perception that computer science is mostly programming or hardware development.)
- beautiful.
The algorithms chosen are search engine indexing, page rank, public key cryptography, error-correcting codes, pattern recognition, data compression, databases, digital signatures, and finally the question of what is computable.
Each easy-to-follow chapter presents each idea with simple charts, tables, or graphs in a familiar context that conveys the essence of the algorithm. The chapter on search engine indexing starts with three short fragments and a simple index of words showing the documents they are in. The word-location trick augments the table to show not only the document but the position in a document of the word which allows a form of ranking. When two words are searched a better match occurs when the two words are closer together. The metaword trick includes document titles in the index. A word in the title probably refers to a more relevant document than one just in the text. Each step continues to show the text and resulting index table. But this is not the whole story and the next chapter on page rank continues to elucidate search algorithms.
One of the most surprising and useful analogies comes in the public key cryptography chapter where the author uses the contrast between the ease of mixing paint and the difficulty of unmixing it to explain the idea behind the Diffie-Hellman algorithm. Each chapter is enlightening and fun to read. The discussion of what is computable is very elementary, referring to programs that answer yes or no, but the long chain of steps needed to get to the conclusion might challenge the seven plus or minus two things we are said to be able to hold in our mind at the same time.
This excellent survey is an outstanding achievement and would make an excellent library acquisition. An appendix gives sources and suggestions for further reading.
Art Gittleman (artg@csulb.edu) is Professor of Computer Science at California State University Long Beach.