Once Upon an Algorithm Read online

  Once we know how to solve a problem, we seldom wonder how the corresponding method was conceived. In particular, when the method is obvious and simple to use, there seems to be no point in reflecting on it. But thinking about how we can solve problems can help us solve unknown problems in the future. Solutions to problems are not always obvious. In hindsight, most solutions seem evident, but what if you didn’t know how to solve the getting-up problem. How would you approach it?

  One crucial observation is that nontrivial problems can be decomposed into subproblems and that the solutions to the subproblems can be combined into a solution for the original problem. The getting-up problem consists of the two subproblems: getting out of bed and getting dressed. We have algorithms for solving both of these problems, that is, moving our body out of the bed and putting on clothes, respectively, and we can combine these algorithms into an algorithm for getting up, but we have to be careful to do it in the right order. Since it is rather difficult to get dressed in bed, we should take the step of getting out of bed first. If you don’t find this example convincing, think about the order in which to take a shower and to get dressed. In this simple example there is only one ordering of the steps that leads to a viable solution, but this is not always the case.

  Problem decomposition is not limited to one level. For example, the problem of getting dressed can be further decomposed into several subproblems, such as putting on pants, a shirt, shoes, and so on. The nice thing about problem decomposition is that it helps us to modularize the process of finding solutions, which means that solutions to different subproblems can be developed independently of one another. Modularity is important because it enables the parallel development of solutions to problems by teams.

  Finding an algorithm for solving a problem is not the end of the story. The algorithm has to be put to work to actually solve the problem. Knowing how to do something and actually doing it are two different things. Some of us are made painfully aware of this difference each morning when the alarm clock rings. Thus there is a difference between an algorithm and its use.

  In computer science each use of an algorithm is called a computation. So does that mean, when we actually do get up, that we are computing ourselves out of bed and into our clothes? That sounds crazy, but what would we say about a robot that did the same thing? The robot needs to be programmed to accomplish the task. In other words, the robot is told the algorithm in a language it understands. When the robot executes its program to get up, wouldn’t we say it carries out a computation? This is not to say that humans are robots, but it does show that people compute when they execute algorithms.

  The power of algorithms derives from the fact that they can be executed many times. Like the proverbial wheel that should not be reinvented, a good algorithm, once developed, is there to stay and serve us forever. It will be reused by many people in many situations to reliably compute solutions to recurring problems. This is why algorithms play a central role in computer science and why the design of algorithms is one of the most important and exciting tasks for computer scientists.

  Computer science could be called the science of problem solving. Even though you won’t find this definition in many textbooks, this perspective is a useful reminder of why computer science affects more and more areas of our lives. Moreover, many useful computations happen outside of machines and are performed by people (without a computer science education) to solve problems. Chapter 1 introduces the concept of computation and, through the story of Hansel and Gretel, highlights its problem-solving and human aspects.

  1

  A Path to Understanding Computation

  What is computation? This question lies at the core of computer science. This chapter provides an answer—at least a tentative one—and connects the notion of computation to some closely related concepts. In particular, I explain the relationship between computation and the concepts of problem solving and algorithms. To this end, I describe two complementary aspects of computation: what it does, and what it is.

  The first view, computation solves problems, emphasizes that a problem can be solved through computation once it is suitably represented and broken down into subproblems. It not only reflects the tremendous impact computer science has had in so many different areas of society but also explains why computation is an essential part of all kinds of human activities, independent of the use of computing machines.

  However, the problem-solving perspective leaves out some important aspects of computation. A closer look at the differences between computation and problem solving leads to a second view, computation is algorithm execution. An algorithm is a precise description of computation and makes it possible to automate and analyze computation. This view portrays computation as a process consisting of several steps, which helps explain how and why it is so effective in solving problems.

  The key to harnessing computation lies in grouping similar problems into one class and designing an algorithm that solves each problem in that class. This makes an algorithm similar to a skill. A skill such as baking a cake or repairing a car can be invoked at different times and thus can be employed repeatedly to solve different instances of a particular problem class. Skills can also be taught to and shared with others, which gives them an even wider impact. Similarly, we can execute an algorithm repeatedly for different problem instances and generate with each execution a computation that solves the problem at hand.

  Dividing Problems into Triviality

  Let us start with the first perspective and consider computation as a process that solves a specific problem. As an example, I use the well-known story of Hansel and Gretel, who were left to die in the woods by their parents. Let’s examine Hansel’s clever idea that allowed him and Gretel to find their way back home after being left behind in the forest. The story unfolds in the context of a famine, when Hansel and Gretel’s stepmother urges their father to lead the children into the forest and abandon them, so that the parents can survive. Having overheard his parents’ conversation, Hansel goes outside later that night and collects several handfuls of small pebbles that he stuffs into his pockets. The next day, during their walk into the forest, he drops the pebbles along the way as markers for the way back home. After the parents have left them, the children wait until it is dark and the pebbles begin to shine in the moonlight. They then follow the pebbles until they return home.

  The story doesn’t end here, but this part provides us with a peculiar example of how a problem is solved using computation. The problem to be solved is one of survival—certainly much more serious than the problem of getting up. The survival problem presents itself as a task of moving from a location in the forest to the location of Hansel and Gretel’s home. This is a nontrivial problem particularly because it cannot be solved in one step. A problem that is too complex to be solved in one step has to be broken down into subproblems that are easy to solve and whose solutions can be combined into a solution for the overall problem.

  The problem of finding the way out of the forest can be decomposed by identifying a sequence of intermediate locations that are close enough to each other that one can easily move between them. These locations form a path out of the forest back to Hansel and Gretel’s home, and the individual movements from one location to the next are easy to achieve. When combined, they yield a movement from the starting location in the forest to the home. This movement solves Hansel and Gretel’s problem of survival in a systematic way. Systematic problem solving is one key characteristic of computation.

  As this example illustrates, a computation usually consists of not just one but many steps. Each of these steps solves a subproblem and changes the problem situation a little bit. For example, each move by Hansel and Gretel to the next pebble is a step in the computation that changes their position in the forest, which corresponds to solving the subproblem of reaching the next target on the path home. While in most cases each individual step will bring the computation closer to the solution, this does not necessarily have to
be the case for every step. Only all steps taken together have to yield the solution. In the story, while each position that Hansel and Gretel go through will generally be closer to home, it is also likely that the path is not a straight line. Some pebbles may even cause detours, for example, to move around obstacles or to cross a river using a bridge, but this does not change the effect of the combined movement.

  The important lesson is that a solution is obtained through a systematic problem decomposition. While decomposition is a key strategy to obtaining a solution to a problem, it is not always sufficient by itself, and solutions may depend on supplementary items—in the case of Hansel and Gretel, the pebbles.

  No Computation without Representation

  If a computation consists of a number of steps, what does each of these steps actually do, and how can all the steps together produce a solution to the given problem? To produce an aggregate effect, each step has to have an effect that the next steps can build on so that the cumulative effect produced by all the steps results in a solution for the problem. In the story the effect of each step is to change Hansel and Gretel’s location, and the problem is solved when the location is finally changed to their home. In general, a step in a computation can have an effect on almost anything, be it concrete physical objects or abstract mathematical entities.

  To solve a problem it is necessary that a computation manipulate a representation of something meaningful in the real world. Hansel and Gretel’s locations represent one of two possible states: all locations in the forest represent the problem state of danger and possibly death, while their home represents the solution state of safety and survival. This is why the computation that brings Hansel and Gretel home solves a problem—it moves them from danger to safety. In contrast, a computation that leads from one place in the forest to another would not achieve that.

  This example has another level of representation. Since the computation that is defined by moves between locations is carried out by Hansel and Gretel, the locations must be recognizable to them, which is why Hansel drops the pebbles along the way. The pebbles represent the locations in a form that enables the computer, that is, Hansel and Gretel, to actually carry out the steps of the computation. It is common to have several layers of representation. In this case we have one that defines the problem (locations) and one that makes it possible to compute a solution (pebbles). In addition, all the pebbles taken together constitute another level of representation, since they represent the path out of the forest back home. These representations are summarized in table 1.1.

  Figure 1.1 Computation is a process for solving a particular problem. Usually, a computation consists of several steps. Starting with a representation of the problem, each step transforms the representation until the solution is obtained. Hansel and Gretel solve the problem of surviving through a process of changing their position step-by-step and pebble-by-pebble from within the forest to their home.

  Figure 1.1 summarizes the problem-solving picture of computation; it shows Hansel and Gretel’s way-finding as an instance of the view that computation manipulates representation in a sequence of steps. In the getting-up problem we also find representations, for example, as location (in bed, out of bed) and as an alarm clock representing time. Representations can take many different forms. They are discussed in more detail in chapter 3.

  Table 1.1

  Computation Representation

  Problem Representation

  Object

  Represents

  Concept

  Represents

  One pebble Location in forest

  Home Location in forest

  Home Danger

  Safety

  All pebbles Path out of forest Path out of forest Problem Solution

  Beyond Problem Solving

  Regarding computation as a problem-solving process captures the purpose of computation but doesn’t explain what computation really is. Moreover, the problem-solving view has some limitations, since not every act of problem solving is a computation.

  As illustrated in figure 1.2, there are computations, and there is problem solving. Although these often overlap, some computations do not solve problems, and some problems are not solved through computation. The emphasis in this book is on the intersection of computations and problem solving, but to make this focus clear, I consider some examples for the other two cases.

  For the first case, imagine a computation consisting of following pebbles from one place to another within the forest. The steps of this process are in principle the same as in the original story, but the corresponding change of location would not solve Hansel and Gretel’s problem of survival. As an even more drastic example, imagine the situation when the pebbles are arranged in a loop, which means the corresponding computation doesn’t seem to achieve anything, since the initial and final positions are identical. In other words, the computation has no cumulative effect. The difference between these two cases and the one in the story is the meaning that is attached to the process.

  Processes without such an apparent meaning still qualify as computation, but they may not be perceived as problem solving. This case is not hugely important, since we can always assign some arbitrary meaning to the representation operated on by a particular computation. Therefore, any computation could arguably be considered problem solving; it always depends on what meaning is associated with the representation. For example, following a loop inside a forest may not be helpful for Hansel and Gretel, but it could solve the problem of getting exercise for a runner. Thus, whether a computation solves a problem is in the eye of the beholder, that is, in the utility of a computation. In any case, whether or not one grants a particular computation the status of problem solving does not affect the essence of computation.

  The situation is markedly different for noncomputational problem solving, since it provides us with further criteria for computation. In figure 1.2 two such criteria are mentioned, both of which are, in fact, very closely related. First, if a problem is solved in an ad hoc way that doesn’t follow a particular method, it is not a computation. In other words, a computation has to be systematic. We can find several instances of this kind of noncomputational problem solving in the story. One example occurs when Hansel and Gretel are held captive by the witch who tries to fatten up Hansel with the goal of eating him. Since she can’t see well, she estimates Hansel’s weight by feeling his finger. Hansel misleads the witch about his weight by using a little bone in place of his finger. This idea is not the result of a systematic computation, but it solves the problem: it postpones the witch’s eating Hansel.

  Figure 1.2 Distinguishing problem solving from computation. A computation whose effect carries no meaning in the real world does not solve any problems. An ad hoc solution to a problem that is not repeatable is not a computation.

  Another example of noncomputational problem solving occurs right after Hansel and Gretel have returned home. The parents plan to lead them into the forest again the next day, but this time the stepmother locks the doors the night before to prevent Hansel from collecting any pebbles. The problem is that Hansel cannot get access to the pebbles that served him so well the first time and that he relied on for finding the way back home. His solution is to find a substitute in the form of breadcrumbs. The important point here is how Hansel arrives at this solution—he has an idea, a creative thought. A solution that involves a eureka moment is generally very difficult, if not impossible, to derive systematically through a computation because it requires reasoning on a subtle level about objects and their properties.

  Unfortunately for Hansel and Gretel, the breadcrumbs solution doesn’t work as expected:

  When the moon came, they set out, but they found no crumbs, for the many thousands of birds which fly about in the woods and fields had picked them all up.1

  Since the breadcrumbs are gone, Hansel and Gretel can’t find their way home, and the rest of the story unfolds.

  However, let us assume for a moment that Han
sel and Gretel could somehow have found their way back home again and that the parents would have tried a third time to leave them behind in the forest. Hansel and Gretel would have had to think of yet another means to mark their way home. They would have had to find something else to drop along the way, or maybe they would have tried to mark trees or bushes. Whatever the solution, it would have been produced by thinking about the problem and having another creative idea, but not by systematically applying a method. This highlights the other criterion for computation, which is its ability to be repeated and solve many similar problems. The method for solving the way-finding problem by following pebbles is different in this regard because it can be executed repeatedly for many different pebble placements.

  To summarize, while the problem-solving perspective shows that computation is a systematic and decomposable process, it is not sufficient to give a comprehensive and precise picture of computation. Viewing computation as problem solving demonstrates how computation can be employed in all kinds of situations and thus illustrates its importance but ignores some important attributes that explain how computation works and why it can be successfully applied in so many different ways.

  When Problems Reappear