Once Upon an Algorithm Page 6
They surely wouldn’t have waited for Hansel to go back home every time he needed a new pebble. Thus an algorithm’s runtime really matters. If the algorithm is too slow, it can become useless from a practical perspective (see chapter 7).
This example also illustrates that space and time efficiency are often interdependent. In this case one can improve the runtime efficiency of the algorithm from quadratic to linear at the expense of storage capacity, that is, using linear storage space, assuming that Hansel’s pockets can store all the pebbles.
When two algorithms solve the same problem, but one has a lower runtime complexity than the other, then the faster algorithm is said to be more efficient (with respect to runtime). Similarly, when one algorithm uses less memory than the other, it is said to be more space efficient. In the example, the linear pebble-placing algorithm is more runtime efficient than the quadratic one, but less space efficient because it fills Hansel’s pockets with pebbles.
Further Exploration
The pebbles in the story of Hansel and Gretel were representations to be used by a way-finding algorithm. Marking a path can have different applications. On the one hand, it can help you find your way back when exploring an unknown territory. This is what happens in the story of Hansel and Gretel. On the other hand, it can help others follow you. This occurs, for example, in J.J.R. Tolkien’s The Lord of the Rings: The Two Towers when Pippin, who was taken prisoner by the orcs with Merry, drops a brooch as a sign for Aragorn, Legolas, and Gimli. Similarly, in the movie Indiana Jones and the Kingdom of the Crystal Skull, Mac secretly drops radio beacons so that he can be followed.
In all three examples, the markers are placed on a more or less open terrain where movements can occur in almost any direction. In contrast, there are also situations when the movement is restricted to a fixed number of connections between junctions. This occurs in Mark Twain’s The Adventures of Tom Sawyer when Tom and Becky explore a cave and place smoke marks on the walls to find their way back out. But they still get lost in the cave. When after several days Becky is too weak to go any further, Tom continues to explore the cave and uses, as a more reliable method, a thread from a kite to always find his way back to Becky. Probably the most famous (and oldest) example of using a thread to not get lost in a labyrinth can be found in the Greek myth of the Minotaur, in which Theseus uses a thread given to him by Ariadne to find his way out of the labyrinth. The same method is used by the Benedictine novice Adso in Umberto Eco’s The Name of the Rose to find his way back through the labyrinth of the monastic library.
It is interesting to compare the different kind of markers used in the stories, and the implications for the corresponding way-finding algorithms. For example, the use of pebbles, brooch, or smoke marks still requires some search to get from one marker to the next, since they only appear at a few places. In contrast, a thread provides a continuous guide that can simply be followed without any search. Moreover, the use of a thread avoids the possibility of a dead-end situation, such as the one described in chapter 1, that can occur when using pebbles or other discrete markers.
Hansel and Gretel’s method is used in modern user interfaces of file systems or query systems, where it is actually known as breadcrumb navigation. For example, browsers in a file system often show a list of the parent or enclosing folders of the current folder. Moreover, search interfaces for email programs or databases often show a list of search terms that apply to the currently shown selection. The action of going back to a parent folder or removing the last search term to get a wider selection corresponds to going to a pebble and picking it up.
Representation and Data Structures
Sherlock Holmes
On Your Way
You are on your way to work. Whether you are driving your car, riding your bike, or walking, you will encounter traffic signs and traffic lights that regulate how you and your fellow commuters share the road. Some of the rules associated with traffic signs are algorithms. For example, a stop sign at a four-way stop street tells you to stop, wait for all other vehicles that have arrived before you to cross the intersection, and then cross the intersection yourself.1 Following the rules associated with traffic signs amounts to executing the corresponding algorithms, which means that the resulting motions are examples of computation. Since many drivers and vehicles are engaged in this activity and since they share the road as a common resource, this is actually an example of distributed computing, but that is not the main point here.
It is remarkable that every day millions of people with completely different goals can effectively coordinate their actions and successfully navigate their ways around one another. Sure, traffic jams and accidents happen on a regular basis, but overall traffic works quite successfully. Even more remarkable is the fact that all this becomes possible through a small set of signs. Placing a red, hexagonally shaped sign containing the word “STOP” at all entries to an intersection enables the coordinated crossing of countless vehicles.
How is it possible that signs have such profound effects? The key observation is that signs carry meaning. For example, a direction sign provides information about the direction of a place of interest. The fact represented by such a sign supports the traveler in making decisions about which turns or exits to take. Other signs provide warnings (for example, of obstacles or curves), prohibit certain actions (such as limiting the maximum speed), and regulate access to shared traffic spaces (such as intersections). In chapter 1 I used the term representation for signs that stand for something else (such as the pebbles that represent locations). From this perspective, signs derive their power from the fact that they are representations.
The effect of a sign does not somehow appear magically by itself but needs to be extracted by some agent. This process is called interpretation, and different agents may interpret a sign in different ways. For example, while a typical traffic participant interprets traffic signs as information or instruction, traffic signs have also become collector’s items. Interpretation is required to understand traffic signs and is also required for all representations used in computer science.
Signs are related to computation in several different ways, emphasizing their importance. First, signs can directly represent computation, as in the case of the stop sign, which designates a particular algorithm for traffic participants to execute. Even if the computation represented by an individual sign is trivial, a combination of such signs has the potential to produce a significant computation as an aggregate. Hansel and Gretel’s pebbles provide an example of this. A single pebble triggers the simple action “Come here if you haven’t visited me before,” whereas all pebbles taken together affect the life-saving movement out of the forest.
Second, a systematic transformation of a sign is a computation.2 For example, crossing out a sign suspends or negates its meaning; this is often done to prohibit actions, such as a bent arrow in a red circle with a red diagonal over it, which forbids a turn. Another example is a traffic light: when it changes from red to green, the meaning changes accordingly from “stop” to “go.”
Finally, the process of interpreting a sign is a computation. This isn’t obvious for simple signs such as pebbles and stop signs but becomes clear when looking at composite signs. One example is the crossed-out sign whose meaning is obtained from the original sign, to which then the meaning of crossing-out has to be applied. Other examples are food-exit signs, whose meanings are obtained as a combination of direction plus the meaning of the restaurant logos that indicate different kinds of food. Interpretation is discussed in chapters 9 and 13. The point here is that signs are entangled in computation in multiple ways. It is therefore a good idea to understand what they are, how they work, and what roles they play in computation. This is the subject of chapter 3.
3
The Mystery of Signs
As illustrated in the first two chapters, computation does its work by manipulating representations, which are symbols or signs that stand for meaningful things. We have seen
how Hansel and Gretel employed pebbles as representations for locations in support of their way-finding algorithm. For that the pebbles had to fulfill a number of requirements that we took for granted. Taking a close look at these requirements will provide a better understanding of what a representation is and how it supports computation.
A representation consists of at least two parts, namely, something that represents and something that is represented. This fact is captured by the notion of a sign. The following are three aspects of signs to keep in mind: signs can operate on multiple levels; signs can be ambiguous (a single sign can represent different things); and one thing can be represented by different signs. This chapter also discusses how different mechanisms enable signs as representations.
Signs of Representation
Do you have any doubt that 1 + 1 equals 2? Probably not, unless you are a time traveler from ancient Rome. In that case the number symbols would look funny to you, and you might instead agree that I + I equals II, that is, if somebody explained to you the meaning of the + symbol, which was not known to the Romans (it was first used in the fifteenth century). And if you could ask an electronic computer, whose number system is based on binary numbers, it would tell you that 1 + 1 equals 10.1 What’s going on here?
This example illustrates that a conversation about even very simple facts of arithmetic requires an agreement about the symbols that represent quantities. This is of course also true for computations with quantities. Doubling 11 yields 22 in the decimal system, which is based on Hindu-Arabic numerals. In ancient Rome one would double II, which yields IV (not IIII),2 and the result from an electronic computer would be 110, since 11 in binary notation represents the number 3, and 110 represents 6.3
What this shows is that the meaning of a computation depends on the meaning of the representation it transforms. For example, the computation that transforms 11 into 110 means doubling if the numbers are interpreted as binary numbers, whereas it means multiplying by 10 if the numbers are interpreted as decimal numbers. And the transformation is meaningless under Roman numeral interpretation because the Romans didn’t have a representation for zero.
Since representation plays such a crucial role in computation, it is important to understand what it really is. And since the word representation is used in many different ways, it is important to be clear about its meaning in computer science. To this end, I solicit help from Sherlock Holmes, the famous detective whose crime-solving methods can reveal much about the way representations work in support of computation. It is typical of Sherlock Holmes to make keen observations of minute details and interpret them in surprising ways. Often these inferences help solve a crime, but sometimes they are just an entertaining way of revealing information for advancing the story. In either case, Sherlock Holmes’s inferences are often based on interpreting representations.
Representations play an important part in one of the most popular and famous Sherlock Holmes adventures, The Hound of the Baskervilles. In typical Sherlock Holmes style, the story begins with a number of observations about a walking stick left behind by a visitor, Dr. Mortimer. Holmes and Watson interpret the engraving on the walking stick, which reads as follows: “To James Mortimer, MRCS, from his friends of the CCH.” Living in England, Holmes and Watson know that “MRCS” stands for, or represents, Member of the Royal College of Surgeons, and from that and with the help of a medical directory, Holmes deduces that “CCH” must stand for Charing Cross Hospital, since Dr. Mortimer has worked there for some time. He also infers that the walking stick must have been given to Dr. Mortimer in appreciation of his service when he left the hospital to become a country practitioner, although it turns out later that this inference is incorrect and that Dr. Mortimer was given the walking stick on the occasion of his wedding anniversary.
The engraving contains three immediately recognizable representations: the two abbreviations and the inscription as a whole that represents the event of Dr. Mortimer’s wedding anniversary. Each of these representations is captured in the form of a sign, a concept introduced by the Swiss linguist Ferdinand de Saussure. A sign consists of two parts, the signifier and the signified. The signifier is what is perceived or presented, whereas the signified is the concept or idea that the signifier stands for. To relate this notion of sign to the idea of representation, we can say that the signifier represents the signified. Since I use the word represent always in the sense of “to stand for,” we can also say that a signifier stands for the signified.
The idea of a sign is important because it succinctly captures the idea of representations. Specifically, the relationship between a signifier and what it represents produces meaning for us—in the case of the walking stick, a part of Dr. Mortimer’s professional history. The signified is often mistakenly assumed to be some physical object in the world, but that is not what Saussure meant by it. For example, the word “tree” does not signify an actual tree but the concept of a tree that we have in our minds.
This aspect makes it quite tricky to write about signs because, on the one hand, text and diagrams that are used to write about signs are signs themselves and, on the other hand, abstract concepts or ideas in the mind can never be shown directly but have to be ultimately represented by signs as well. In the literature about semiotics, the theory of signs and their meaning, the idea of a sign is often illustrated by a diagram containing the word “tree” as an example of a signifier and a drawing of a tree as the thing signified by “tree.” However, the drawing is itself a sign for the concept of a tree, and therefore the diagram can be misleading, since “tree” is not a signifier of the drawing but of what the drawing signifies, which is the concept of a tree.
Since we are bound to using language to talk about language and representation, there is no way out of this dilemma, and we can never present ideas or concepts other than through some linguistic means. Whether we want to talk about a signifier or a signified, we always have to use signifiers to do that. Fortunately, we can get around this problem most of the time by putting quote marks around a word or phrase that is used as a signifier or by typesetting it in a special form such as italics. The quote marks have the effect of referring to the word or phrase as such, without interpreting it. In contrast, a word or phrase used without quote marks is interpreted as what it stands for, that is, a signified concept.
Thus “tree” refers to the four-letter word, whereas the word without the quote marks refers to the concept of a tree. The distinction between a quoted word standing for itself and its unquoted use standing for what it means is referred to as the use-mention distinction in analytic philosophy. The unquoted word is actually used and denotes what it represents, while the quoted word is only mentioned and does not refer to what it stands for. Quoting stops interpretation from acting on the quoted part and thus allows us to clearly distinguish between talk about a word and its meaning. For example, we can say that “tree” has four letters, whereas a tree does not have letters but branches and leaves.
The seemingly simple concept of a sign contains a lot of flexibility. For example, signs can operate on multiple levels, signs can have multiple meanings, and the link between signifier and signified can be established in different ways. I describe these three aspects in the following sections.
Signs All the Way Down
In addition to the three signs on the walking stick that I have already identified—“MRCS” signifying Member of the Royal College of Surgeons, “CCH” signifying Charing Cross Hospital, and the whole inscription signifying Dr. Mortimer’s wedding anniversary—there are actually a few more signs at work here. First, “Member of the Royal College of Surgeons” signifies membership in a professional society, and similarly, “Charing Cross Hospital” signifies a specific hospital in London (the concept, not the building). But that is not all. In addition, “MRCS” also signifies the surgeon society membership, and “CCH” also signifies the London hospital.
Thus an abbreviation has two possible meanings and can have two differ
ent signifieds, since it extends to the signified of its signified. What does that mean? Since the signified of “CCH” is the phrase “Charing Cross Hospital,” which is itself a signifier for a London hospital, “CCH” can represent the London hospital by combining two representations in which the signified of the first is the signifier for the second. In a similar way, “MRCS” combines two levels of representation into one, since it represents the surgeon society membership by referring to the signified of “Member of the Royal College of Surgeons.”
Why does this matter, and what does this have to do with computer science? Recall the two forms of representation distinguished in chapter 1: problem representation and computation representation. The fact that a sign can combine two levels of representation into one makes it possible to add meaning to computations that are otherwise purely symbolic. I explain this idea with an example that uses the number representation discussed earlier.
Viewed as a binary number, the signifier “1” represents the number one on the level of computation representation. This number can represent different facts in different contexts and thus has different problem representations. If you are playing roulette, this could be, for example, the amount of money you bet on black. The transformation that appends a 0 to the 1 means, on the level of computation representation, to double the number one to two. In the context of the problem representation the transformation can also mean that black did come up and that you won your bet and now have twice the amount of money available.