You are here

Once Upon an Algorithm: How Stories Explain Computing

Martin Erwig
MIT Press
Publication Date: 
Number of Pages: 
[Reviewed by
Allen Stenger
, on

(Revised version, 10/18/2017)

Analogously to a popular math book, this appears to be a “popular computer science book”, that attempts to convey to the general reader what computer scientists do and why it is important. The method or gimmick here is to look at popular stories and abstract the everyday knowledge there to get computer science structures and algorithms.

I think this method works well for explaining, at least at a high level, some common computer science concepts in everyday terms. I think it is less successful at explaining why computer science is important, why it is hard, and why there is such a profession. If you explain that computer scientists kind of do the same things as action movie heroes, you run the risk of trivializing the subject. I also think it presses the analogies too far in some cases; after setting up a good concrete basis, it ventures too far into abstraction.

For example, one story is Indiana Jones and the Last Crusade. This is a quest story in which a number of things are sought, so it leads naturally to a consideration of search methods, which in computer science are closely tied to sort methods. There are probably dozens of different sort algorithms in computer science, and whole books on the subject, and the reason no single “best” method has emerged is that they all have their strengths and weaknesses. In particular the execution times of each sort method usually vary a lot, and often the average time is much less than the worst-case time. There are also a number of subtleties depending on operational conditions; for example, if the data is already almost in order, some algorithms can take advantage of this to finish the sort quickly, while others are oblivious. None of this comes out in the present book.

The book is also not good at explaining why the computer science approach is useful. After all, it’s doubtful Indiana Jones would have had an easier time of it if he had a good computer science background. Much of the intricacy of computer science comes from the need for speed and from the need to specify in advance how to handle all possible abnormal cases. In human problems we deal with much smaller sets of data, and we mostly depend on human judgement to handle the unexpected. None of this comes out in the book. The author probably doesn’t mean to imply that computer science is useful in everyday life (all of his examples are analogies rather than special cases), but the explanations of where or how computer science is useful are weak, in a couple of ways. These explanations occur in “Why does it matter?” sections in the Introduction, but these are far away from the exposition. They also are not closely tied to the exposition; for example, sorting gets a whole chapter in the book but is not mentioned in the corresponding “Why does it matter?” section.

The overall approach of the book is valuable. I have quibbles with some of the details. The book starts out on the first page (p. vii) with the bold statement that computer science is “the study of systematic problem solving.” Don’t other scientific and intellectual disciplines do systematic problem solving too? The book does make a curious statement, on p. 114, that “mergesort is the best possible solution for the problem of sorting. It is therefore an optimal algorithm.”, although it also hedges in the footnotes on p. 306 by saying “there can be multiple optimal algorithms”. Most computer scientists would not single out one method as optimal. On p. 143 the book describes a musical score as “an algorithm to produce music.” I would say rather than the score is a notation or description of music, and there are numerous algorithms used by musicians and computers to produce music from this notation. That’s how the same melody can be realized on multiple types of instruments. The description of data typing (Chapters 14–15) is confusing, and overlooks the subject of object-oriented programming, which is the very rigorous way to handle this. The index is weak; for example, the famous traveling salesman problem and knapsack problem get good discussions in the book but are not top-level entries in the index; you have to think to look them up under “problem examples”.

Bottom line: despite its weaknesses, this is a pretty good book as popularizations go. The general reader will get some glimmering of what goes on inside computers, and especially will get an appreciation that there is much more to computers than calculations, displaying web pages, and playing games.

Allen Stenger is a math hobbyist and retired software developer. He is an editor of the Missouri Journal of Mathematical Sciences. His personal web page is His mathematical interests are number theory and classical analysis.


Part I Algorithms

Computation and Algorithms — Hansel and Gretel
1 A Path to Understanding Computation
2 Walk the Walk: When Computation Really Happens

Representation and Data Structures — Sherlock Holmes
3 The Mystery of Signs
4 Detective’s Notebook: Accessory after the Fact

Problem Solving and its Limitations — Indiana Jones
5 The Search for the Perfect Data Structure
6 Sorting out Sorting
7 Mission Intractable

Part II Languages

Language and Meaning — Over the Rainbow
8 The Prism of Language
9 Finding the Right Tone: Sound Meaning

Control Structures and Loops — Groundhog Day
10 Weather, Rinse, Repeat
11 Happy Ending Not Guaranteed

Recursion — Back to the Future
12 A Stitch in Time Comes First
13 A Matter of Interpretation

Types and Abstraction — Harry Potter
14 The Magical Type
15 A Bird’s Eye View: Abstracting from Details