Once Upon an Algorithm Page 4

  Hansel and Gretel are faced with the problem of finding their way back home twice. Except for the practical problems caused by the lack of pebbles, the second instance could be solved in the same way as the first, namely, by following a series of markers. There is nothing really surprising about this fact, since Hansel and Gretel are simply applying a general method of way-finding. Such a method is called an algorithm.

  Let us take a look at the algorithm that was used by Hansel and Gretel to find their way home. The exact method is not explained in detail in the original fairy tale. All we are told is the following:

  And when the full moon had risen, Hansel took his little sister by the hand, and followed the pebbles which shone like newly-coined silver pieces, and showed them the way.

  A simple algorithm that fits this characterization is given, for example, by the following description:

  Find a shining pebble that was not visited before, and go toward it. Continue this process until you reach your parents’ house.

  An important property of an algorithm is that it can be used repeatedly by the same or a different person to solve the same or a closely related problem. An algorithm that generates a computation with a physical effect is useful even if it solves only one specific problem. For example, a recipe for a cake will produce the same cake over and over again. Since the output of the algorithm is transient—the cake gets eaten—reproducing the same result is very useful. The same holds for the problem of getting out of bed and dressed; the effect of the algorithm has to be reproduced every day, although likely with different clothes and at a different time on weekends. This also applies to Hansel and Gretel. Even if they are brought to the same place in the forest as on the first day, getting home has to be recomputed by repeating the algorithm to solve the exact same problem.

  The situation is different for algorithms that produce nonphysical, abstract results, such as numbers. In such a case one can simply write down the result and look it up the next time it is needed instead of executing the algorithm again. For an algorithm to be useful in such situations it must be able to solve a whole class of problems, which means that it must be possible to apply the method to several different, but related, problems.2

  In the story the method is general enough to solve many different way-finding problems, since the exact positions of the pebbles do not matter. No matter where exactly in the forest the parents lead the children to, the algorithm will work in every case3 and consequently will cause a computation that solves Hansel and Gretel’s survival problem. Much of the power and impact of algorithms comes from the fact that one algorithm gives rise to many computations.

  The notion of an algorithm is one of the most important concepts in computer science because it provides the foundation for the systematic study of computation. Accordingly, many different aspects of algorithms are discussed throughout this book.

  Do You Speak “Algorithmish”?

  An algorithm is a description of how to perform a computation and must therefore be formulated in some language. In the story the algorithm is only marginally mentioned. Hansel certainly has the algorithm in his head and might have told Gretel about it, but the algorithm is not written down as part of the story. However, the fact that an algorithm can be written down is an important property because it enables the reliable sharing of the algorithm and thus allows many people to use it to solve problems. The ability to express an algorithm in some language supports the proliferation of computation because instead of one person producing many computations, it facilitates many people’s producing even more computations. If the language in which the algorithm is expressed can be understood by a computing machine, then the proliferation of computation seems almost limitless, bounded only by the resources needed to build and operate computers.

  Does the getting-up algorithm need a description in a language? Probably not. Through repeated execution we all have internalized the steps to the point that we execute them unconsciously and don’t need a description. However, for some parts of this algorithm there do exist descriptions, often given as a sequence of pictures. Think about tying a tie or arranging a sophisticated braided hairstyle. If you do this for the first time and no one is available to demonstrate the technique, you can learn the skill from such a description.

  The ability to express an algorithm in a language has another important effect. It allows the systematic analysis and formal manipulation of algorithms, which is the subject of computer science theory and programming languages research.

  An algorithm must be expressible in a language that can be understood by the computer to execute it. Moreover, the description must be finite, that is, it is bounded and doesn’t go on forever. Finally, each of its individual steps must be effective, that is, whoever executes the algorithm must be able to understand and perform all the steps. Hansel and Gretel’s algorithm is clearly finite, since it contains only a few instructions, and the individual steps are also effective, at least when we assume that the pebbles are placed within viewing distance of one another. One might have some doubts about the requirement to always find a pebble that was not visited before; this can be difficult because of the need to remember all the previously encountered pebbles. This requirement could be easily realized, though, by simply picking up each pebble immediately after it has been visited. However, this would then be a different algorithm. Incidentally, that algorithm would have made it easy for Hansel and Gretel to find their way back on the second day, since Hansel would have held onto all the pebbles. The slightly changed algorithm would have made the story as told by the Brothers Grimm impossible (depriving us, alas, of a classic fairy tale).

  A Wish List

  In addition to the defining characteristics, there are several desirable features for algorithms. For example, an algorithm should always produce a computation that terminates and that delivers correct results. Since Hansel has placed a finite number of pebbles that mark the way to the parents’ house, an execution of the described algorithm will terminate because it visits each pebble no more than once. Surprisingly, however, it might not produce a correct result in all cases because the process could get stuck.

  Figure 1.3 A path that illustrates a possible dead end in an algorithm. Left: Visiting the pebbles in the reverse order leads to Hansel and Gretel’s home. Right: Since pebbles B, C, and D are all within viewing distance from one another, Hansel and Gretel could choose to go from D to B and then to C. At that point, however, they are stuck because no pebble that they haven’t visited before is visible from C. Specifically, they cannot reach A, which is the next pebble on the path home.

  As stated, the algorithm does not say which pebble exactly to go to. If the parents are leading Hansel and Gretel not in a straight line but, say, along a zig-zag path into the forest, it could happen that from one pebble several other pebbles are visible. Which pebble should Hansel and Gretel go to in such a case? The algorithm doesn’t say. Under the assumption that all pebbles are placed in viewing distance from one another, we can encounter the following situation, illustrated in figure 1.3.

  Imagine a series of pebbles A, B, C, and D, placed by Hansel on their way into the forest. Suppose that A can be seen from B, and B can be seen from C, but A is too far away to be visible from C. (This is indicated in the figure by the circles of visibility around pebbles B and C.) Moreover, suppose that D is within viewing distance from both B and C. This means that when Hansel and Gretel arrive at D, they can see the two pebbles B and C and have a choice to make. If they choose to go to C, then they will find B next and finally A, and everything will be fine (see left part of figure 1.3). However, if they choose B instead of C—which is possible according to the algorithm, since B is a visible pebble not visited before—they can get into trouble because if they next choose C—which again is visible and has not been visited yet—they will be stuck at C. This is because the only pebbles that they can see from C are B and D, both of which have already been visited and therefore cannot be chosen, accordi
ng to the algorithm (see right part of figure 1.3).

  Of course, we could try to fix the algorithm by adding instructions to backtrack in cases like this and choose a different alternative, but the point of this example is to illustrate a case in which a given algorithm does not produce a correct result. It also shows that the behavior of an algorithm is not always easy to predict, which makes the design of algorithms a challenging and interesting endeavor.

  The termination of algorithms is not an easy-to-recognize property either. If we remove the condition in the algorithm to find only nonvisited pebbles, a computation can easily slip into a nonterminating back-and-forth movement between two pebbles. One might object that Hansel and Gretel would never do such a silly thing and would recognize such a repeating pattern. This might be true, but then they would not be following the exact algorithm and would, in fact, be deliberately avoiding a previously visited pebble.

  Whereas the case of a nonterminating back-and-forth between two pebbles would be easy to spot, the problem can be much more difficult generally. Imagine a path taken by the parents into the forest that crosses itself a few times. The resulting pebble placement would include several loops, each of which Hansel and Gretel could be caught in; only by remembering visited pebbles could they be certain to avoid such loops. Chapter 11 considers the problem of termination in more detail.

  Questions of correctness and termination do not seem that important for the getting-up algorithm, but people have been known to put on nonmatching socks or to violate the rules for correctly buttoning a shirt. And if you persist in repeatedly hitting the snooze button, the getting-up algorithm will not even terminate.

  Starting the Day

  Most people’s day doesn’t really start before they’ve had breakfast. Cereal, fruit, eggs with bacon, juice, coffee—whatever is on the menu, chances are that breakfast needs some form of preparation. Some of these preparations can be described by algorithms.

  If you like to vary your breakfast, for example, by adding different toppings to your cereal or brewing different amounts of coffee, the algorithm that describes the preparation must be able to reflect this flexibility. The key to providing controlled variability is to employ one or more placeholders, called parameters, that are replaced by concrete values whenever the algorithm is executed. Using different values for a placeholder causes the algorithm to produce different computations. For example, a parameter “fruit” can be substituted by different fruits on different days, allowing the execution of the algorithm to produce blueberry cereal as well as banana cereal. The getting-up algorithm also contains parameters so that we are not forced to wake up at the same time and wear the same shirt every day.

  If you are grabbing coffee from a coffee shop on your way to work, or if you are ordering breakfast in a restaurant, algorithms are still employed in producing your breakfast. It is just that other people have to do the work for you. The person or machine that is executing an algorithm is called a computer and has a profound effect on the outcome of a computation. It may happen that a computer is unable to execute the algorithm if it doesn’t understand the language in which the algorithm is given or if it is unable to perform one of its steps. Imagine you are a guest on a farm, and the algorithm for getting your morning milk involves your milking a cow. This step might prove prohibitive.

  But even if a computer can execute all the steps of an algorithm, the time it takes to do so matters. In particular, the execution time can vary substantially between different computers. For example, an experienced cow milker can extract a glass of milk faster than a novice. However, computer science mostly ignores these differences because they are transient and not very meaningful, since the speed of electronic computers increases over time—and novice cow milkers can get more experienced and thus faster. What is of great importance, however, is the difference in execution time between different algorithms for the same problem. For example, if you want to get a glass of milk for everyone in your family, you could fetch each glass separately, or you could fetch a milk can once and then fill all glasses at the breakfast table. In the latter case you have to walk the distance to the stable only twice, whereas in the former case you have to walk it ten times for a family of five. This difference between the two algorithms exists independently of how fast you can milk or walk. It is thus an indicator for the complexity of the two algorithms and can be the basis for choosing between them.

  In addition to execution time, algorithms may also differ with regard to other resources that are required for their execution. Say your morning drink is coffee and not milk, and you have the option to brew coffee with a coffee maker or use a French press. Both methods require water and ground coffee, but the first method additionally requires coffee filters. The resource requirements for different milking algorithms are even more pronounced. Getting fresh milk requires a cow, whereas milk bought at a grocery store requires a fridge for storing it. This example also shows that computation results can be saved for later use and that computation can be sometimes traded for storage space. We can save the effort of milking a cow by storing previously drawn milk in a fridge.

  The execution of an algorithm has to pay for its effect with the use of resources. Therefore, in order to compare different algorithms for the same problem, it is important to be able to measure the resources they consume. Sometimes we may even want to sacrifice correctness for efficiency. Suppose you are on your way to your office and you have to grab a few items from the grocery store. Since you are in a hurry, you leave the change behind instead of storing the coins returned to you. The correct algorithm would exchange the exact amount of money for the bought items, but the approximation algorithm that rounds up finishes your transaction faster.

  Studying the properties of algorithms and their computations, including the resource requirements, is an important task of computer science. It facilitates judging whether a particular algorithm is a viable solution to a specific problem. Continuing with the story about Hansel and Gretel, I explain in chapter 2 how different computations can be produced with one algorithm and how to measure the resources required.

  2

  Walk the Walk: When Computation Really Happens

  In the previous chapter we saw how Hansel and Gretel solved a problem of survival by computing their way back home. This computation transformed their position systematically in individual steps, and it solved the problem by moving from a position in the forest, representing danger, to the final position at home, representing safety. The back-to-home computation was the result of executing an algorithm to follow a path of pebbles. Computation happens when algorithms get to work.

  While we now have a good picture of what computation is, we have only seen one aspect of what computation actually does, namely, the transformation of representation. But there are additional details that deserve attention. Therefore, to expand understanding beyond the static representation through algorithms, I discuss the dynamic behavior of computation.

  The great thing about an algorithm is that it can be used repeatedly to solve different problems. How does this work? And how is it actually possible that one fixed algorithm description can produce different computations? Moreover, we have said that computation results from executing an algorithm, but who or what is executing the algorithm? What are the skills needed to execute an algorithm? Can anybody do it? And finally, while it is great to have an algorithm for solving a problem, we have to ask at what cost. Only when an algorithm can deliver a solution to a problem fast enough and with the resources allocated is it a viable option.

  Creating Variety

  Getting back to Hansel and Gretel, we’ve seen that their pebble-tracing algorithm can be used repeatedly and in different situations. Let us now take a closer look at how this actually works. Since the description in the algorithm is fixed, some part of this description must account for the variability in computations. This part is called a parameter. A parameter in an algorithm stands for some concrete value, and when an algorit
hm is executed, a concrete value must be substituted for the parameter in the algorithm. Such a value is called an input value, or just input, for the algorithm.

  For example, an algorithm for making coffee may use a parameter number to represent the number of cups to be brewed so that the algorithm’s instructions can refer to this parameter. Here is an excerpt from such an algorithm:1

  Fill in number cups of water.

  Fill in 1.5 times number tablespoons of ground coffee.

  To execute this algorithm for three cups of coffee, you have to substitute the input value 3 for the parameter number in the algorithm’s instructions, which yields the following specialized version of the algorithm:

  Fill in 3 cups of water.

  Fill in 1.5 times 3 tablespoons of ground coffee.

  The use of the parameter makes the algorithm applicable in a variety of different situations. Each situation is represented by a different input value (in the example, the number of cups of coffee to be brewed) to be substituted for the parameter, and the substitution adapts the algorithm to the situation represented by the input value.

  Hansel and Gretel’s algorithm uses a parameter for the pebbles placed in the forest. I did not specify the parameter exactly before because the instruction “Find a pebble not visited before” clearly referred to the pebbles placed by Hansel. The parameter can be made explicit by using the following instruction instead: “Find a pebble from the pebbles-placed-by-Hansel not visited before.” For each execution of the algorithm, the parameter pebbles-placed-by-Hansel is then replaced by the pebbles that Hansel has dropped—at least we can think of it this way. Since we obviously cannot physically place pebbles into the algorithm description, we treat the parameter as a reference or pointer to the input value. A pointer is a mechanism to access the input value; it tells us where to look for the input value when the algorithm needs it. In the way-finding algorithm, the input value is to be found on the forest floor. In the coffee-making algorithm, we have the input value in our mind, and whenever the parameter refers to it, we retrieve it. Nonetheless, the idea of substitution provides a useful analogy that helps to make the relationship between an algorithm and a computation concrete.