I know two young teenagers who possess more knowledge than any scientist, philosopher, or scholar of ages past. They are my sons. No, I am not a doting father who marvels at how extraordinarily gifted his children are. But these two kids have in their pockets devices that connect them with the vastest repository of information that has ever been created. There is no factual question they cannot answer, now that they have mastered the art of knowing where to look on the internet. They can translate from and to foreign languages without having to browse through hefty dictionaries—which we still keep in the house so that they know how things were, only a few years back. News, from anywhere, reach them in an instant. They can communicate with their peers before you know it, no matter where in the world they may live. They can plan their goings out in perfect detail. Alas, they can waste their time with abandon playing games or following trends that change so fast that I do not know why they matter.
All the above have become possible thanks to the huge advances in digital technology. Today we carry more computing power in our pockets than was used to ferry humans to the moon. As these two teenagers show, the changes in our lives have been immense; predictions for the future vary from utopias, where people will really not need to work, to dystopias, where the privileged few will lead fulfilling lives, with the rest being condemned to inconsequential torpor. Thankfully, we are able to shape this future, and an important factor in our ability to do this is how conversant we are with the technologies that underlie the achievements and the changes before us. Although we may lose sight of it in the bustle of our everyday lives, we live in the best period of human history. We are healthier than we have ever been, and expect to live longer, on average, than any generation that has ever lived. Despite the iniquity of glaring inequality, huge swathes of humanity have gotten rid of the shackles of poverty. We have never been closer to one another, both virtually and literally. We may decry the commercialism of mass global tourism, but cheap travel allows us to experience different cultures and visit places that we could once marvel about only in coffee table books. All this progress can and should continue.
To partake in this progress, however, it is not enough to use digital technology. We must be able to understand it. First, for the eminently practical reason that it offers excellent career opportunities. Second, because even if we don’t care for a career in technology, we must know its underlying principles to appreciate its potential and shape our own role in it. Digital technology is enabled as much by its hardware, the physical components that make up computers and digital devices, as by its software, the programs that run on it. The backbone of programs are the algorithms that they implement: the set of instructions that describe the way to solve particular problems (if this does not look like a definition of what an algorithm is, don’t worry, we have the rest of the book to fill out the details). Without algorithms, computers would be useless, and none of modern technology would exist.
What we need to know changes through time. For most of human history, schooling was not deemed necessary at all. Most people were illiterate, and if they were taught something, it would be mastery of some practical skill or scripture. In the beginning of the nineteenth century, more than 80 percent of the world’s population was completely unschooled; now the vast majority has attained several years of school, and it is projected that by the end of the century, the proportion of unschooled people in the world will fall to zero. The years we spend on education have also increased. While in 1940 less than 5 percent of Americans had a bachelor’s degree, by 2015 almost a third of them did.1
Back in the nineteenth century, no school would teach molecular biology because nobody knew anything about it; DNA wasn’t discovered until well into the twentieth century. It now forms part of what we accept as the canon of an educated person’s learning. Similarly, even though algorithms were discovered in antiquity, few people troubled with them until the advent of modern computers. The author firmly believes that we have reached a point where algorithms are inside the core of what we consider to be essential knowledge. Unless we know what they are and how they work, we cannot understand what they can do, how they can affect us, what to expect from them, what their limits are, and what they require in order to work. In a society that increasingly functions thanks to algorithms, it behooves us as informed citizens to be knowledgeable about them.
Digital technology is enabled as much by its hardware, the physical components that make up computers and digital devices, as by its software, the programs that run on it. The backbone of programs are the algorithms that they implement.
It is also possible that learning algorithms helps us in another way. If learning mathematics introduces us to a way of rigorous reasoning, a familiarity with algorithms introduces us to a new way of algorithmic thinking: a way of reasoning to solve problems in a practical way so that efficient implementations of algorithms as programs can run fast in computers. The focus on designing processes that are practical and efficient can be a useful mental tool, even if we are not professional programmers.
This book aims to introduce algorithms to a nonspecialist audience in a way that the reader will understand how they really work. Its purpose is not to describe the effects of algorithms in our lives; there are other books that do a great job of depicting how improved processing of big data, artificial intelligence, and the weaving of computing devices into the fabric of our everyday lives may change the human condition. Here we are not interested in what may happen but rather the how this can happen. To do that, we’ll present real algorithms and show not only what they do but also how they actually function. Instead of hand waving, we’ll provide detailed explanations.
A familiarity with algorithms introduces us to a new way of algorithmic thinking: a way of reasoning to solve problems in a practical way so that efficient implementations of algorithms as programs can run fast in computers.
To the question, “What are algorithms?” the answer is surprisingly simple. They are particular ways to solve our problems. These ways to solve our problems can be described in easy steps so that computers can execute them with amazing speed and efficiency. Yet there is nothing magical about these solutions. The fact that they comprise simple elementary steps means that there is no reason why they should be beyond the grasp of most people.
Indeed, the book does not assume knowledge of material beyond that commonly taught in high schools. Some mathematics does appear in the following pages because you cannot talk seriously about algorithms without some notation. Any concepts that are commonplace in algorithms but are not that common outside computer science are explained in the text.
The late physicist Stephen Hawking wrote in the introduction of his best-selling book A Brief History of Time, published in 1988, “Someone told me that each equation I included in the book would halve the sales.” This sounds pretty ominous for the present book because mathematics does occur more than once. Yet I decided to press ahead, for two reasons. First, while the level of mathematics required for Hawking’s physics is at the university level or beyond, the mathematics presented here is much more accessible. Second, as the purpose of this book is to show not just what algorithms are for but how they really work too, the reader should get to share some of the vocabulary we use when we discuss algorithms. And this vocabulary does include some mathematics. The notation is not the prerogative of the technical clerisy, and familiarity with it will help dispel any mystique surrounding the subject; in the end, we’ll see that it mostly comes down to being able to talk about things in a precise quantitative way.
It is impossible to cover the whole subject of algorithms with a book like this, but it is possible to provide an overview and introduce a reader to algorithmic thinking. The first chapter lays the ground by introducing what algorithms are and how we can gauge their efficiency. We can say at the outset that an algorithm is a finite sequence of steps that we can perform with a pen and paper, and this plain definition would not be far from the truth. Chapter 1 starts from there, while also exploring the relationship between algorithms and mathematics. A key difference between the two is practicality; in algorithms, we are interested in practical ways to solve our problems. This means that we need to be able to measure how practical and efficient our algorithms are. We’ll see that these questions can be carefully framed through the notion of computational complexity; this will inform the discussion of algorithms in the rest of the book.
The next three chapters look at three of the most essential application areas of algorithms. Chapter 2 covers algorithms that deal with the solution of problems relating to networks, called graphs, of things. These problems may include finding your way in a road network or sequence of links connecting you to somebody on a social network. They also include problems in other areas that are not immediately obvious in terms of their relationship: DNA sequencing and scheduling tournaments; this will illustrate that distinct problems can be solved efficiently using the same tools.
Chapter 3 and chapter 4 explore how to search for things and put things in order. These may seem prosaic, yet they are among the most important applications of computers. Computers spend a lot of time sorting and searching, but we are largely oblivious to this fact exactly because they are an integral, invisible part of most applications. Sorting and searching also offer us a glimpse of an important facet of algorithms. For many problems, we know of more than one algorithm to solve them. We choose among the available algorithms based on their particular characteristics; some algorithms are more suitable for certain problem instances than others. It is therefore instructive to see how different algorithms, with different characteristics, go about solving the same problem.
The following two chapters present important applications of algorithms on a large scale. Chapter 5 picks up graphs again to explain the PageRank algorithm, which can be used to rank web pages in order of significance. PageRank was the algorithm used by Google when it was founded. The success of the algorithm at ranking web pages in search results played a critical role in the phenomenal success of Google as a company. Fortunately, it is not difficult to grasp how PageRank works. It will give us the opportunity to see how an algorithm can solve a problem that on first impression, does not seem amenable to a computer solution: How do we judge what is important?
Chapter 6 introduces one of the most active areas in computer science: neural networks and deep learning. Successful applications of neural networks are reported in popular media. Stories pique our interest by describing systems that perform tasks such as image analysis, automatic translation, or medical diagnosis. We’ll start out simple, from individual neurons, building up bigger and bigger neural networks that are able to perform more and more complex tasks. We’ll see that they all work based on some fundamental principles. Their efficacy rises from the interconnection of many simple components and the application of an algorithm that lets neural networks learn.
After sketching what algorithms can do, the epilogue explores the limits of computation. We know that computers have performed amazing feats and expect so much more from them in the future, yet are there things that they cannot do? The discussion of the limits of computing will allow me to offer a more precise explanation of the nature of algorithms and computing. We said that we could describe it as a finite sequence of steps that can be performed with a pen and paper, but what kind of steps could these be? And how close is the pen-and-paper analogy with what algorithms really are?