Jump directly to the Content
Jump directly to the content
Article

Science in Focus: Mitchel T. Keller


9 Algorithms That Changed the Future, Part 3

What computer scientists do.

In 9 Algorithms that Changed the Future: The Ingenious Ideas that Drive Today's Computers, John MacCormick sets out to provide accessible descriptions of nine profoundly important algorithms. Beyond that, he also offers an insight into what what computer scientists do. As he writes in the conclusion, students in introductory computer science courses (and most other people) seem to equate computer science with programming and hardware design. However, after reading MacCormick's book, one can have little doubt that programming is merely an ancillary skill to a computer scientist. Far more important is the ability to think creatively; once an algorithm has been invented, any skilled programmer can implement it.

To make the cut for the book, an algorithm had to meet three criteria. First, it had to be one that ordinary users encounter on a daily basis. Second, the algorithm needed to address "concrete, real-world problems." And finally, MacCormick gave priority to algorithms relating to computer science theory. Since hardware is more the territory of computer engineers, this criterion isn't too great of a restriction. The other criteria, however, eliminate many of the algorithms—e.g., sorting algorithms and Dijkstra's shortest path algorithm—that mathematicians and computer scientists might expect to see in a book with this title. Since those expecting to see these foundational algorithms are not really part of this book's target audience, it seems MacCormick's choice was reasonable. By sacrificing the classics, he has crafted a compelling story of the creative genius that underlies everyone's daily computer usage.

The algorithms included are truly ubiquitous. They encompass many aspects of searching the web; automatically recognizing graphical patterns efficiently; authenticating data; and transmitting, storing, and protecting data efficiently. In each case, MacCormick identifies a handful of essential "tricks" that allow the algorithm to succeed. I'd prefer he use "insights" or "techniques" instead of "tricks," but in reality we call these "tricks" in casual conversation all the time. The possible downside to casting these techniques as tricks is downplaying the creativity and hard work involved in algorithm design. In chapters 2 through 9, the key ideas behind these algorithms are introduced using accessible analogies. For areas where mathematics plays a significant role, MacCormick uses several layers of analogy, beginning at a level where no mathematics is present and building from there to give the reader a small-scale version of what's involved.

The final algorithm of the book is more of a non-algorithm. MacCormick looks at the question of what can be solved efficiently by an algorithm, and not just what can be solved today. This chapter will push some readers beyond their comfort zone, but it is accessible to most as it addresses the famed Church-Turing thesis. This is the statement that there are some yes-no questions which no general-purpose computer can be programmed to answer. This idea of undecidability is a profound one and was the subject of a 1936 paper in which British mathematician Alan Turing laid the foundation for what we now know as computer science. The Church-Turing thesis also raises important questions for artificial intelligence and the limits of the human mind. If we could program a computer to do anything the human brain can do, but there are things a computer cannot do, then what does that imply about the supposedly limitless potential of the human mind?

Mitchel T. Keller is a Visiting Fellow in the Department of Mathematics at the London School of Economics and Political Science, where he is supported by a Marshall Sherfield Fellowship.

See also Part 1 of this round, by Cary Gray, and Part 2, by Andrew M. C. Dawes.

Most ReadMost Shared