Once Upon an Algorithm
2017 Massachusetts Institute of Technology
All rights reserved. No part of this book may be reproduced in any form by any electronic or mechanical means (including photocopying, recording, or information storage and retrieval) without permission in writing from the publisher.
This book was set in Garamond by the author using the LATEX document preparation system. Printed and bound in the United States of America.
Library of Congress Cataloging-in-Publication Data
Names: Erwig, Martin, author.
Title: Once upon an algorithm : how stories explain computing / Martin Erwig.
Description: Cambridge, MA : MIT Press, [2017] | Includes bibliographical references and index.
Identifiers: LCCN 2016053945 | ISBN 9780262036634 (hardcover : alk. paper)
Subjects: LCSH: Computer algorithms-Popular works.
Classification: LCC QA76.9.A43 E78 2017 | DDC 005.1-dc23 LC record available at https://lccn.loc.gov/2016053945
10 9 8 7 6 5 4 3 2 1
When people ask about my work, the conversation quickly turns to the question of what computer science is. To say computer science is the science of computers is misleading (though strictly speaking not incorrect) because most people will take computer to mean PC or laptop and conclude that computer scientists spend their time constructing hardware. On the other hand, defining computer science as the study of computation is simply kicking the can down the road, since it immediately raises the question of what computation is.
Over the years, I have come to realize that teaching by just introducing concept after concept doesnt work very well; it is simply too abstract. Nowadays, I typically start by describing computer science as the study of systematic problem solving. Everybody knows what a problem is, and everybody has seen solutions as well. After explaining this view through an example, I often get the chance to introduce the concept of an algorithm, which allows me to point out important differences between computer science and mathematics. Most of the time, I dont need to talk about programming languages, computers, and related technical matters, but even if it comes to that, the concrete problem makes it easy to illustrate these concepts. Once Upon an Algorithm is an elaboration of this approach.
Computer science is a relatively new member of the science club, and sometimes it seems it has not yet earned the respect granted to serious scientific disciplines like physics, chemistry, and biology. Think of a movie scene involving a physicist. You will probably see someone discussing complicated formulas written on a blackboard or supervising an experiment wearing a lab coat. The physicist is shown as a reputable scientist whose knowledge is treasured. Now imagine a similar scene involving a computer scientist. Here you will likely see some nerdy guy sitting in a dark, messy room and staring at a computer screen. He is frantically typing on a keyboard, probably trying to break some code or password. In both scenes, an important problem is being solved, but while the physicist might provide some plausible explanation of how it can be solved, the solution of the computer problem remains mysterious, often magical, and much too complex to be explained to a nonspecialist. If computer science is unexplainable to laypeople, why would anyone ever try to know more about it or understand it?
The subject of computer science is computation, a phenomenon that affects everybody. I am not talking only about cell phones, laptops, or the internet. Consider folding a paper airplane, driving to work, cooking a meal, or even DNA transcription, a process that occurs in your cells millions of times while you are reading this sentence. These are all examples of computationa systematic way of problem solvingeven though most people would not perceive them as such.
Science provides us with a basic understanding of how the natural world works, and it gives us the scientific method for reliably establishing that knowledge. What applies to science in general holds for computer science, too, especially since we encounter computation in so many different forms and so many different situations. A basic understanding of computation thus provides benefits similar to a basic knowledge of physics, chemistry, and biology in making sense of the world and tackling many real-world problems more effectively. This aspect of computation is often referred to as computational thinking.
A major goal of this book is to emphasize the general nature of computation and thus the wide applicability of computer science. My hope is that this will spark a broader interest in computer science and a desire to learn more about it.
I first identify computation in everyday activities and then explain corresponding computer science concepts through popular stories. The everyday situations are taken from a typical workday: getting up in the morning, having breakfast, commuting to work, episodes at the workplace, a doctors appointment, a hobby activity in the afternoon, having dinner, and reflecting on the days events in the evening. Each of these fifteen vignettes introduces a book chapter. The chapters then explain the computation concepts using seven popular stories. Each story spans two or three chapters and deals with a specific topic of computer science.
The book has two parts: algorithms and languages. These are the two main pillars on which the concept of computation rests. summarizes the stories and the computer science concepts they illustrate.
We all appreciate a good story. Stories console us, give us hope, and inspire us. They tell us about the world, make us aware of the problems we face, and sometimes suggest solutions. Stories can also provide guidance for our lives. When you think about what stories have to teach us, you probably think about love, conflict, the human condition. But I also think about computation. When Shakespeares Juliet asks, Whats in a name? she is on to an important question about representation. Albert Camuss The Myth of Sisyphus raises the question of how to face the absurdity of life and also how to detect a never-ending computation.
Table 1
Story | Chapters | Topics |
Hansel and Gretel | Computation and Algorithms |
Sherlock Holmes | Representation and Data Structures |
Indiana Jones | Problem Solving and Its Limitations |
Over the Rainbow | Language and Meaning |
Groundhog Day | Control Structures and Loops |
Back to the Future | Recursion |
Harry Potter | Types and Abstraction |
Stories have multiple layers of meaning. They often include a computational layer. Once Upon an Algorithm is an effort to unveil this layer and offer readers a new perspective on stories and computation. I hope that stories will be appreciated for their computational content and that this novel point of view will spark interest in computer science.
The idea for Once Upon an Algorithm arose from many conversations with friends, students, colleagues, and people I talk to on the bus on my way to work. I thank all of them for their patience in listening to my explanations about computer science and for their friendly impatience when the explanations became too long and complicated. The goal of writing a widely accessible book about computer science was fueled to a large degree by these experiences.
Over the last decade Ive had the opportunity to work with many high school students as summer interns, which provided additional encouragement. These internships were supported by several grants from the National Science Foundation, to which I am grateful for its support of scientific research and science education in the United States.
Next page