You are here

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

Publisher: 
Princeton University Press
Number of Pages: 
248
Price: 
27.95
ISBN: 
9780691147147

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.

Date Received: 
Tuesday, November 22, 2011
Reviewable: 
Yes
Include In BLL Rating: 
Yes
John MacCormick
Publication Date: 
2012
Format: 
Hardcover
Audience: 
Category: 
General
Art Gittleman
12/26/2011
BLL Rating: 

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

Publish Book: 
Modify Date: 
Thursday, May 31, 2012

Dummy View - NOT TO BE DELETED