You are here

Nine Algorithms that Changed the Future: the Ingenious Ideas that Drive Today's Computers

John MacCormick
Publisher: 
Princeton University Press
Publication Date: 
2012
Number of Pages: 
248
Format: 
Hardcover
Price: 
27.95
ISBN: 
9780691147147
Category: 
General
BLL Rating: 

The Basic Library List Committee suggests that undergraduate mathematics libraries consider this book for acquisition.

[Reviewed by
Art Gittleman
, on
12/26/2011
]

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:

  1. used by ordinary computer users, like a search but unlike a compiler.
  2. applied to a specific problem, unlike generic sorting algorithms.
  3. related to the theory of computer science. (This is to counter the perception that computer science is mostly programming or hardware development.)
  4. 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.

Foreword ix
Chapter 1. Introduction: What Are the Extraordinary Ideas Computers Use Every Day? 1
Chapter 2. Search Engine Indexing: Finding Needles in the World's Biggest Haystack 10
Chapter 3. PageRank: The Technology That Launched Google 24
Chapter 4. Public Key Cryptography: Sending Secrets on a Postcard 38
Chapter 5. Error-Correcting Codes: Mistakes That Fix Themselves 60
Chapter 6. Pattern Recognition: Learning from Experience 80
Chapter 7. Data Compression: Something for Nothing 105
Chapter 8. Databases: The Quest for Consistency 122
Chapter 9. Digital Signatures: Who Really Wrote This Software? 149
Chapter 10. What Is Computable? 174
Chapter 11. Conclusion: More Genius at Your Fingertips? 199
Acknowledgments 205
Sources and Further Reading 207
Index 211

Dummy View - NOT TO BE DELETED