Once Upon an Algorithm

by Martin Erwig

  Computation is used for the systematic solving of problems. Although electronic computers have facilitated the unprecedented growth and reach of computation, they are just one tool of computing. The concept of computing is more general and more widely applicable. As we have seen, Hansel and Gretel already knew how to execute an algorithm and how to successfully employ abstractions in representing paths through pebbles. Sherlock Holmes was a master of signs and representations, and he manipulated data structures to solve crimes. And Indiana Jones didn’t employ an electronic computer for any of his exciting searches. The language of music might not have solved any problem directly, but it incorporates every bit of syntax and semantics you can imagine. Phil Connors may not have known any theoretical computer science, yet he faced the same problem that illustrates the fundamental limits of computation: the unsolvability of the halting problem. Marty McFly and Doc Brown lived recursion, and Harry Potter revealed to us the magic power of types and abstraction.

  The heroes of these stories may not be heroes of computing, but their stories have told us a lot about what computation is. As this book ends, I want to leave you with one more story—the story of computer science. This is a story about abstractions for conquering the concept of computation. Its main protagonist is the algorithm, which can systematically solve problems through the transformation of representations. It does that by skillfully applying its basic tools, control structures and recursion. Although problems can be solved in different ways, the algorithm doesn’t settle for any specific solution but aspires to be as general as possible by employing its secret weapon, the parameter. However, any of its concrete missions is a constant struggle, since the algorithm always faces serious opposition from its arch enemy complexity:

  Computation = Story(algorithm, solving problems)

  The story unfolds as new and larger problems push the algorithm to its limits. But in its struggle it enjoys the friendship and support of its relatives from the abstraction family: its sister efficiency, who counsels it about the prudent use of precious resources; its brother type, who shields it relentlessly from programming errors and incorrect inputs; and its wise grandmother language, who bestows on it expressiveness and makes sure it is understood by its trusted companion the computer, on whom it relies for executing any of its plans:

  Computer Science = Story(abstractions, capturing computation)

  The algorithm is not all powerful and cannot solve all problems, and it is particularly vulnerable to inefficiency and errors. But it is well aware of this fact. And this knowledge about its own limitations makes it strong and confident about the adventures that lie ahead.

  Further Exploration

  The magic in Harry Potter illustrates the concepts of types and typing rules and how they can help making predictions about the future. A rigorous system of magic can be found in L. E. Modesitt Jr.’s series of fantasy novels The Saga of Reduce, where magic is a person’s ability to control the chaos and order that is inherent in all matter. The protagonist in Jim Butcher’s book series The Dresden Files is a private detective and wizard who investigates cases involving supernatural phenomena. The stories contain different types of magic, laws of magic, and tools for magic.

  Many examples of creatures with specific abilities, which can be described as types, can be found in the world created by J. R. R. Tolkien in his novels The Lord of the Rings and The Hobbit. The superheroes in the X-Men comic series and corresponding movies have special abilities that are well defined and interact in a precisely defined way with the natural world. Some of the superheroes define a type that has exactly one element, namely, themselves. Other types have multiple members.

  Using a device incorrectly often amounts to a type error and can lead to malfunction. This is regularly exploited for dramatic effect, as in the movie The Fly, where the improper use of a teleportation device causes mixing of the DNA of a human and a fly. Type errors also occur when people change or switch roles, playing on stereotypes associated with the roles. For example, in the movie Freaky Friday, the minds of a teenager and her mother switch their bodies, which leads to behaviors that violate the expectations associated with the roles of teenager and adult. In Mark Twain’s The Prince and the Pauper, a prince switches roles with a poor boy.

  Abstractions come in many different forms. Dioramas are abstractions often used to represent important events in history. Some examples occur in the movie Dinner for Schmucks. A voodoo doll is an abstraction of a person and is used to inflict pain on the person over a distance. Examples occur in Indiana Jones and the Temple of Doom and in Pirates of the Caribbean: On Stranger Tides. In Jim Butcher’s The Dresden Files, voodoo dolls are used several times. Similarly, an avatar is representations of oneself that can act in distant environments, which is a major theme of the movie Avatar. The movie Inside Out represents the mind as a space inhabited by five people that personify basic emotions.

  Money is an abstraction of value and is an essential tool for exchanging goods in economies. The fact that money is a socially constructed abstraction and works only when all participants agree on its value is nicely illustrated in stories that use non-traditional currencies, as in Mad Max 2, where gasoline is the major currency, or in the movie In Time, where one’s own life span is used as a currency. In Frank Herbert’s Dune, water and spice are currencies, and Douglas Adam’s The Hitchhiker’s Guide to the Galaxy contains a number of weird currency examples.

  Abstractions of behavioral rules can be found in Isaac Asimov’s I, Robot collection of short stories in the form of three laws of robotics that are intended to ensure that robots serve humans well without harming them. These laws represent an abstraction of morality. The stories illustrate the application of these laws and their limitations, which has led to modification and extensions of the laws. And in Max Barry’s Lexicon a secret society has developed a novel language that is not a tool for communicating ideas but for controlling the actions of other people. While natural languages typically provide abstractions for describing the world, the special language in Lexicon, is based on abstractions for neurochemical reactions that steer human actions, similar to how some magic spells can directly affect behavior.

  Glossary

  This glossary summarizes important terms in the book. The entries are grouped in sections by story and major concepts. Some entries appear in more than one section.

  Important terms used in definitions are labeled with a section letter indicating the section where they themselves are defined. For instance, algorithmA indicates that the term algorithm is defined in section A.

  A. Computation and Algorithms

  algorithm. A method for solving a problemA. An algorithm is applicable to different problem examples and must be given by a finite description in a languageD that is understandable by a computerA. All steps of the method must be effective. ExecutionA of an algorithm on a particular problem example generates a computation.A An algorithm should terminateE and produce a correctA result for any problem it is executed on, but that is not always the case, and these properties are difficult to ensure. An algorithm that is understandable by a machine is called a programA.

  computation. A process that solves a problemA in a number of steps by systematically transforming a representationA of the problem. A computation is what happens during the executionA of an algorithmA by a computerA.

  computer. A person, machine, or other actor that can executeA an algorithmA. A computer must understand the languageD in which the algorithm is given.

  correctness. The property of an algorithmA to always produce the desired result for any given valid inputA. If an algorithm gets stuck or doesn’t terminateE for some input, it is not a correct solution to a problemA.

  execution. The process of following the steps in an algorithmA for a particular problemA example. Execution is performed by a computerA and generates a computationA.

  input. The variable part of a problemA that distinguishes different problem examples. The input is part of the pro
blem representationA and can consist of several parts. An algorithmA applied to a specific input leads to a computationA for the problem instance for that input. In the algorithm, the input is represented by parametersA.

  parameter. A name used by an algorithmA to refer to its inputA.

  problem. A representationA of a situation, deemed in need of a solution, that facilitates solutions through computationA. Refers to both individual problem examples that are subject to transformation by computationA and the class of all such problems that can be the inputA for an algorithmA.

  program. An algorithmA that can be understood and executedA by a machine.

  representation. An entity that stands for something in the real world. A representation must be modifiable by the steps of a computationA. See also representationB.

  runtime. A measure for the number of steps an executionA of an algorithmA is expected to take. Expressed as a rule that captures how the runtime is related to the size of the inputA. Commonly occurring runtime measures are linearC, quadraticC, logarithmicC, and exponentialC.

  worst case. The longest possible runtimeA of a computationA generated by an algorithmA. The worst case serves as an estimate to judge whether an algorithmA is efficient enough to produce a solution to a problemA.

  Concept How It Appears in Hansel and Gretel

  Algorithm Method to follow pebbles

  Computation Finding a way home

  Computer Hansel and Gretel

  Correctness Tracing pebbles leads home and doesn’t get stuck or lead to a loop

  Execution When Hansel and Gretel perform the pebble-tracing algorithm

  Input Placement of all the pebbles

  Parameter The expression “shining pebble that was not visited before”

  Problem Survival; finding the way home

  Program A description of the pebble-tracing algorithm in machine-readable form

  Representation Locations and pebbles

  Runtime Steps needed to follow the pebbles home

  Worst case Hansel and Gretel have to visit each pebble at most once

  B. Representation and Data Structures

  array. A data structureB for representing a collection of items. Akin to a table with two rows, one row of which contains names or numbers (indices) for the items stored in the array. An indexB is used to look up items in an array. An array is a good choice for implementing a setB because it facilitates constant-time lookup for items. But, since an array has to reserve space for all possible items, it can be used only if the number of possible items that might be stored in it is small. Is also used to represent the buckets in bucket sortC.

  data structure. A representationB used by an algorithmA that provides distinct access and manipulation. Frequently used data structures are arraysB, listsB, and treesB.

  data type. A description of a representationB whose behavior is given through a set of operations that can manipulate the representationB. Must be implemented by a data structureB. One data type can often be implemented by different data structures, which typically implement the operations with different runtimesA. Frequently used data types are setsB, dictionariesB, stacksB, and queuesB.

  dictionary. A data typeB for associating information with keysB. Provides operations for inserting, removing, and updating the information for specific keys as well as an operation for looking up information given a key. A setB is a special form of dictionary in which the elements are the keys and which doesn’t store any information with those keys.

  icon. A signB that represents based on similarity with the signifiedB.

  index. A signB that represents based on a law-like relationship with the signifiedB. Also, a way to look up elements in an arrayB.

  key. A value used to find information in a dictionaryB. See also search keyC.

  list. A data structureB for representing a collection of elements in a specific order. The elements can be accessed one by one, starting with the element at the front of the list. Can also be viewed as a treeB in which each nodeB (except the last) has exactly one child. Can be used to implement data typesB such as stacksB, queuesB, or setsB.

  node. An element in a data structureB that is connected to other elements. Examples are the elements of treesB and listsB. In a treeB the elements that can be directly accessed from a node are called its children, and the node from which a node can be accessed is called its parent. Each node can have at most one parent, and the topmost node in a tree, the root, has no parent. Nodes with no children are called leaves.

  priority queue. A data typeB for a collection from which elements are removed in the order of a given priority. Realizes the HIFO (highest in, first out) principle for accessing elements in a collection.

  queue. A data typeB for a collection from which elements are removed in the same order in which they were inserted. Realizes the FIFO (first in, first out) principle for accessing elements in a collection.

  representation. A signB that stands for something in the real world. See also representationA.

  set. A data typeB for representing a collection of elements that provides operations for insertion, removal, and finding of elements. Can be represented as a dictionaryB in which the elements are the keysB. The set data type is important, since it facilitates the representation of properties.

  sign. A specific form of representationB consisting of a signifierB (its visible part) and a signifiedB (what the signifier stands for).

  signified. The part of a signB represented by the signifierB. Not a concrete object in the world but a concept about objects that people have in their minds.

  signifier. The part of a signB that is perceived and that stands for the signifiedB. One signifier can represent different concepts.

  stack. A data typeB for a collection from which elements are removed in the opposite order in which they were inserted. Realizes the LIFO (last in, first out) principle for accessing elements in a collection.

  symbol. A signB that stands for the signifiedB based on an arbitrary convention.

  tree. A data structureB for representing a collection of elements as a hierarchy. Its elements are called nodesB. Any node higher up in the hierarchy is connected to zero or more nodes lower in the hierarchy and to at most one node higher in the hierarchy.

  Concept How It Appears in The Hound of the Baskervilles

  Array Representation of suspect set with check marks

  Data structure List of suspects, family tree

  Data type Set of suspects

  Dictionary Sherlock Holmes’s notebook with entries about the suspects

  Icon Portrait of Sir Hugo Baskerville; map of the Devonshire moor

  Index The hound’s footprints and the cigar ashes at the crime scene

  Key Names of suspects

  List The list of suspects Mortimer→Jack→Beryl→Selden→…

  Node Name of family member in the family tree

  Priority queue Inheritance ordering for the heirs of Baskerville

  Queue Watson’s list of things to do at Baskerville Hall

  Representation Suspect list or array; map of the Devonshire moor

  Set Set of suspects

  Sign Engraving on Dr. Mortimer’s walking stick

  Signified Charing Cross Hospital (by signifier CCH)

  Signifier Acronym CCH (for Charing Cross Hospital)

  Stack Repeatedly computing descendants of children before siblings

  Symbol A number (2704) for a taxi cab

  Tree Family tree of the Baskervilles

  C. Problem Solving and Its Limitations

  approximation algorithm. An algorithmA for computingA solutions that might not be completely correctA but are good enough in most cases.

  balanced tree. A treeB in which all leaves have about the same distance from the root (their distances differ by at most 1). A balanced tree has the smallest height among all trees with the same number of nodesB; it is as wide as possible. This shape guarantees that if a binary search treeC is balanced, finding elements has logar
ithmic runtimeC in the worst caseA.

  binary search. An algorithmA for finding an element in a collection. Compares the element to be found with one element in the collection, which partitions the collection into two regions. Depending on the outcome of the comparison, the search continues in only one of the two regions. When elements for splitting are chosen well so that they always partition the search space into two regions of approximately the same size, as in a balanced binary search treeC, binary search takes logarithmic runtimeC in the worst caseA.

  binary search tree. A binary treeC with the property that for each nodeB in the treeB, all the nodes in its left subtree are smaller, and all the nodes in its right subtree are larger.

  binary tree. A treeB in which each nodeB has at most two children.

  bucket sort. A sorting algorithmA that scans the listB to be sorted and places each element into one of a number of specifically reserved and initially empty spaces (buckets). After all list elements have been placed into buckets, the buckets are inspected in order, and all the elements from nonempty buckets are put into the result list. Bucket sort typically uses an arrayB to represent the buckets. It requires that the set of elements that may possibly occur in the list be not too large, so that each potential bucket can be assigned only a few or even only one element. In that case bucket sort has linear runtimeC.

  divide-and-conquer. An algorithmA schema in which the solution is obtained by splitting the input into separate parts, solving the problems for the parts independently of one another, and then combining the solutions for the parts into a solution for the original problemA. Divide-and-conquer is not an algorithm itself, but an algorithm structure. MergesortC and quicksortC are examples.

  exponential runtime. An algorithmA has exponential runtime when its execution time doubles (or increases by a factor greater than 1) whenever the size of the inputA grows by 1. This means that if the size of the input increases by 10, the algorithm will take 1,000 times longer. Algorithms with exponential runtime are not practical solutions, since they work only for inputs of small size.