Once Upon an Algorithm Read online

  Once Upon an Algorithm

  Once Upon an Algorithm

  How Stories Explain Computing

  Martin Erwig

  The MIT Press

  Cambridge, Massachusetts

  London, England

  © 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

  Contents

  Copyright

  Preface

  Acknowledgments

  Introduction

  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 Computes Fine

  13 A Matter of Interpretation

  Types and Abstraction — Harry Potter

  14 The Magical Type

  15 A Bird’s Eye View: Abstracting from Details

  Glossary

  Notes

  Index

  Preface

  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 doesn’t 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 don’t 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 computation—a systematic way of problem solving—even 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 doctor’s appointment, a hobby activity in the afternoon, having dinner, and reflecting on the day’s 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. Table 1 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 Shakespeare’s Juliet asks, “What’s in a name?” she is on to an important question about representation. Albert Camus’s 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

  Part I

  Hansel and Gretel 1, 2 Computation and Algorithms

  Sherlock Holmes 3, 4 Representation and Data Structures

  Indiana Jones 5, 6,
7 Problem Solving and Its Limitations

  Part II

  Over the Rainbow 8, 9 Language and Meaning

  Groundhog Day 10, 11 Control Structures and Loops

  Back to the Future 12, 13 Recursion

  Harry Potter 14, 15 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.

  Acknowledgments

  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 I’ve 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.

  In researching the material for Once Upon an Algorithm I have relied on the internet, in particular, Wikipedia (wikipedia.org) and the TV Tropes website (tvtropes.org). Thanks to all those contributors for their commitment and enthusiasm in sharing their knowledge with the world.

  While I was writing this book, Eric Walkingshaw, Paul Cull, and Karl Smeltzer read some of the chapters and provided expert feedback on content and writing style. I want to thank them for their helpful advice. Thanks also to Jennifer Parham-Mocello for reading some of the chapters and testing several of the examples with her students in a college freshman class. I also thank my son, Alexander, for proofreading the manuscript and providing expert advice on questions related to Harry Potter. Most of this book was written during a sabbatical from my position at Oregon State University. I thank my department and the university for their support for this project.

  Turning the idea for this book into reality was a much greater challenge than I had anticipated. My sincere thanks to Marie Lufkin-Lee, Katherine Almeida, Kathleen Hensley, and Christine Savage at MIT Press for supporting this project and helping me with it along the way.

  Finally, I am fortunate to be married to my most patient and candid reader. My wife, Anja, encouraged me throughout the adventure of this book project. She always had an open ear for my questions, which more often than not were quite nerdy and abstract. She read many drafts and patiently tried to rein me in whenever my writing was too academic and relied too much on technical jargon. The completion of Once Upon an Algorithm owes more to her than to anyone else, and I dedicate this book to her.

  Introduction

  Computation plays a prominent role in society now. But unless you want to become a computer scientist, why should this prompt you to learn more about it? You could simply enjoy the technology powered by computation and take advantage of its benefits. You likely also don’t study avionics to make use of air travel or seek a medical degree to benefit from the achievements of modern health care.

  However, the world we live in consists of more than man-made technology. We still have to interact with nonautonomous objects ruled by physical laws. Therefore, it is beneficial to understand the basics of mechanics simply to predict the behavior of objects and to safely navigate one’s environment. A similar case can be made for the benefits of studying computation and its related concepts. Computation is not only revealed in computers and electronic gadgets but also occurs outside of machines. In the following I briefly discuss some of the major computer science principles and explain why they matter.

  Computation and Algorithms

  I invite you to perform the following simple exercise. For this you need a ruler, a pencil, and a piece of (quadrille-ruled) paper. First, draw a horizontal line that is 1 inch long. Then draw a vertical line of the same length, perpendicular to the first, starting at one of its ends. Finally, connect the two open ends of the lines you drew with a diagonal to form a triangle. Now measure the length of the diagonal just drawn. Congratulations; you have just computed the square root of 2. (See figure 1.)

  What does this exercise in geometry have to do with computation? As I explain in chapters 1 and 2, it is the execution of an algorithm by a computer that brings about a computation. In this example, you acted as a computer that executed an algorithm to draw and measure lines, which led to the computation of . Having an algorithm is crucial because only then can different computers perform a computation repeatedly and at different times. An important aspect of computation is that it requires resources (such as pencil, paper, and a ruler) and takes time to carry out. Here again, having an algorithmic description is important because it helps in analyzing the resource requirements for computations.

  Figure 1 Computing the square root of 2 using a pencil and a ruler.

  Chapters 1 and 2 explain

  what algorithms are,

  that algorithms are used for systematic problem solving,

  that an algorithm needs to be executed by a computer (human, machine, etc.) to produce a computation,

  that the execution of algorithms consumes resources.

  Why does it matter?

  Recipes are examples of algorithms. Whenever you make a sandwich, bake a chocolate cake, or cook your favorite dish by following the instructions of a recipe, you are effectively executing an algorithm to transform the raw ingredients into the final product. The required resources include the ingredients, tools, energy, and preparation time.

  Knowledge about algorithms makes us sensitive to questions about the correctness of a method and what its resource requirements are. It helps us identify opportunities for improving processes in all areas of life through the (re)organization of steps and materials. For instance, in the geometric square root computation, we could have omitted drawing the diagonal line and just measured the distance between the two unconnected end points.

  In cooking the improvement can be as simple and obvious as saving trips to the fridge by planning ahead or gathering ingredients ahead of time. You could plan how to use your oven or stove more efficiently and save time by parallelizing steps, such as preheating the oven or washing the salad while the potatoes are cooking. These techniques also apply to many other areas, from simple assembly instructions for furniture to organizational processes for running an office or managing a factory floor.

  In the realm of technology, algorithms control basically all the computations in computers. One prominent example is data compression, without which the transmission of music and movies over the internet would be nearly impossible. A data compression algorithm identifies frequent patterns and replaces them with small codes. Data compression directly addresses the resource problem of computation by reducing the space required to represent songs and movies and thus also the time it takes to load them over the internet. Another example is Google’s page-rank algorithm, which determines the order in which search results are presented to a user. It works by assessing the importance of a web page through counting how many links point to it and weighing how important those links are.

  Representation and Data Structures

  One might expect that numerical computations are carried out with the help of numbers because we use the Hindu-Arabic numeral system, and machines work with 0s and 1s. So the geometric method for computing with the help of lines might be surprising. The example demonstrates, however, that one and the same thing (for example, a quantity) can be represented in different ways (number symbols or lines).

  The essence of a computation is the transformation of representation. I explain in chapter 3 what representations are and how they are employed in comp
utations. Since many computations deal with large amounts of information, I explain in chapter 4 how collections of data can be efficiently organized. What complicates this question is the fact that any particular data organization may support some forms of accessing the data efficiently but not others.

  Chapters 3 and 4 discuss

  different forms of representation,

  different ways of organizing and accessing data collections,

  the advantages and disadvantages of different data organizations.

  Why does it matter?

  Measurements of ingredients in recipes can be given by weight or by volume. These are different forms of representation, which require different cooking utensils (scales or measuring cups) for properly executing the recipe/algorithm. As for data organization, the way your fridge or pantry is organized has an impact on how fast you can retrieve all the ingredients required for the recipe. Or consider how the question of representation applies to the recipe itself. It may be given as a textual description, through a series of pictures, or even in the form of a YouTube video. The choice of representation often makes a big difference in the effectiveness of algorithms.

  In particular, the question of how to arrange a collection of items or people has many applications, for instance, how to organize your desk or garage to help you find items more quickly or how to organize the book shelves in a library. Or consider the different ways you wait in line: in a grocery store (standing in a queue) or at a doctor’s office (sitting in a waiting room having picked a number) or when boarding an airplane (multiple queues).

  In the realm of technology, spreadsheets are among the most successful programming tools. The organization of data in tabular form has contributed to much of their success because it supports the quick and easy formulation of sums over rows and columns and represents the data and computation results for them in one place. On the other hand, the internet, one of the most transformative inventions of the late twentieth century, organizes web pages, computers, and the connections between them as a network. This representation supports flexible access to information and efficient transmission of data.