Once Upon an Algorithm

by Martin Erwig

  generate-and-test. An algorithmA schema that consists of two major phases. In the first phase, it produces potential solutions, which are then systematically checked during the second phase. Generate-and-test is not an algorithm itself, but an algorithm structure. Trying out all combinations for a combination lock is an example, as is trying out all combinations for solving a knapsack problemC.

  greedy algorithm. An algorithmA is called greedy if it always picks the currently best available option. Picking elements from a sorted list for solving a knapsack problemC is an example.

  insertion sort. A sorting algorithmA that repeatedly picks the next element from an unsorted listB and inserts it at the right place in the sorted list. Insertion sort has quadratic runtimeC in the worst caseA.

  intractable problem. A problemA for which only algorithmsA with exponential runtimeC are known. Examples are the knapsack problemC and the traveling salesman problem.

  knapsack problem. An example of an intractable problemC. The task is to fill a knapsack of limited capacity with as many items as possible to maximize the total value of all items that fit in the knapsack.

  linear runtime. An algorithmA has linear runtimeA when its execution time grows proportionally to the size of the inputA. Linear runtime is better than linearithmic runtimeC but not as good as logarithmic runtimeC. Finding the smallest element in a list has linear runtime in the worst caseA.

  linearithmic runtime. An algorithmA has linearithmic runtimeA when its execution time grows proportionally to the size of inputA multiplied by the logarithm of the size. Linearithmic runtime is not quite as good as linear runtimeC but much better than quadratic runtimeC. MergesortC has linearithmic runtime in the worst caseA.

  logarithmic runtime. If an algorithmA has logarithmic runtime, its runtimeA increases only by 1 for inputA twice the size. Logarithmic runtime is much faster than linear runtimeC. For example, binary searchC in a balancedC binary search treeC has logarithmic runtime.

  lower bound. The complexity of a problemA. Gives the growth rate of the minimum number of steps any algorithmA must take to solve a problem. Any algorithm whose worst-caseA runtimeA is the same as the lower bound is an optimal algorithmC.

  mergesort. A divide-and-conquerC sorting algorithmA that first splits the listB to be sorted into two sublists of equal length, then sorts these sublists, and finally merges the sorted sublists into the sorted result list. Mergesort has linearithmic runtimeC in the worst caseA. Since the lower boundC for sorting is also linearithmic, mergesort is an optimal algorithmC for sorting.

  optimal algorithm. An algorithmA whose worst-caseA runtimeA is the same as the lower boundC of the problemA it is solving.

  quadratic runtime. An algorithmA has quadratic runtimeA when its execution time grows proportionally to the square of the size of inputA. Quadratic runtime is worse than linearithmic runtimeC but much better than exponential runtimeC. Insertion sortC and selection sortC have quadratic runtime in the worst caseA.

  quicksort. A divide-and-conquerC sorting algorithmA that first splits a listB to be sorted into two sublists that each contain all the elements that are, respectively, smaller and larger than a chosen pivot element. These two lists are then themselves sorted, and the results are concatenated, with the pivot element in the middle, into the sorted result list. Quicksort has a quadratic runtimeC in the worst caseA, but performs very well in practice and has linearithmic runtimeC in the average case.

  search key. A piece of information that identifies something to be found. In some cases it is derived (then it is an indexB); in other cases it is a separate, unrelated value (then it is a symbolB). Identifies the boundary that separates relevant from irrelevant elements with regard to the current search. See also keyB.

  selection sort. A sorting algorithmA that repeatedly finds the minimum from an unsorted listB and puts it at the end of the sorted list. Selection sort has quadratic runtimeA in the worst caseA.

  trie. A treeB data structureB for implementing setsB or dictionariesB that represents each keyB as a sequence of nodesB. A trie is particularly efficient when the stored keys share common parts.

  Concept How It Appears in Indiana Jones

  Approximation algorithm Using an inflatable boat as a parachute

  Balanced tree Some of the search trees for letter frequencies

  Binary search Finding tiles on the tile floor

  Binary (search) tree Representing letter frequencies for the words Iehova, etc.

  Bucket sort Computing letter frequencies using an array

  Divide-and-conquer Reducing the search for Henry Jones, Sr., to Venice

  Exponential runtime Determining the exact weight of the idol

  Generate-and-test Systematically trying out all weight combinations

  Greedy algorithm Trying weights in descending order

  Insertion sort Sorting the tasks for finding the Well of Souls

  Intractable problem Finding the exact weight of the idol with a balance scale

  Knapsack problem Collecting treasure items in the temple of the crystal skull

  Linear runtime Executing the list of tasks

  Linearithmic runtime Finding the idol’s weight by trying

  Logarithmic runtime Finding a letter frequency in a binary tree

  Lower bound Minimum time to sort list of tasks

  Mergesort Sorting the tasks for finding the Well of Souls

  Optimal algorithm Using mergesort for sorting

  Quadratic runtime Using selection sort for sorting

  Quicksort Sorting the tasks for finding the Well of Souls

  Search key Venice; Iehova

  Selection sort Sorting the tasks for finding the Well of Souls

  Trie Tile floor

  D. Language and Meaning

  ambiguity. A property of a grammarD. When a sentenceD can have two or more syntax treesD.

  abstract syntax. The hierarchical structure of a sentenceD, represented as a syntax treeD. The abstract syntax of a languageD as defined by a grammarD is the set of all syntax trees that can be built using the grammar.

  compositionality. A property of the semantics definitionD of a languageD. A semantics definition is compositional if the meaning of a sentenceD is obtained from the meanings of its parts. Implies that the structure of a sentence determines how the meanings of its parts are combined in a systematic way.

  concrete syntax. The appearance of a sentenceD as a sequence of terminalsD (or arrangements of visual symbols).

  derivation. A sequence of sentential formsD, each of which is obtained from the previous one by substituting a nonterminalD according to a grammar ruleD. The first element of a derivation must be a nonterminal, and its last element must be a sentenceD.

  grammar. A set of grammar rulesD that map nonterminalsD to sentential formsD. Defines a languageD. One language can be defined by different grammars. The language defined by a grammar consists of all sentencesD for which a derivationD from the start symbolD exists.

  grammar rule. A grammar rule has the form nt → RHS where nt is a nonterminalD and RHS is a sentential formD. Used to substitute nonterminals in sentential forms as part of a derivationD.

  language. A set of sentencesD, each of which has an appearance as a sequence of words or an arrangement of visual symbols (concrete syntaxD) and an internal structure (abstract syntaxD or syntax treeD). The definition of a language is given by a grammarD. A language is the set of all sentences that can be derivedD from the grammar’s start symbolD. Some, but not all, languages also have a semantics definitionD.

  nonterminal. A symbol that occurs on the left-hand side of a grammar ruleD; a symbol that can be substituted by a sentential formD. The start symbolD of a grammarD is a nonterminal.

  parsing. The process of identifying the structure of a sentenceD and representing it as a syntax treeD.

  semantic domain. A set of values that are relevant in a particular application area. Used in the semantics definitionD of a languageD.

  semantics defin
ition. A mapping of the syntax treesD of a languageD to elements of a semantic domainD.

  sentence. An element of a languageD given by a sequence of terminalsD.

  sentential form. A sequence of terminalsD and nonterminalsD. Occurs on the right side of a grammar ruleD.

  start symbol. A designated nonterminalD of a grammarD. Any sentenceD of a languageD defined by a grammar must be obtainable through a derivationD from the start symbol.

  syntax. The definition of which sentencesD belong to a languageD. Typically defined by a grammarD, which consists of rules for forming or recognizing a sentenceD. The rules define both the concrete syntaxD and the abstract syntaxD of a language.

  syntax tree. A hierarchical representation of the structure of a sentenceD in the form of an upside-down treeB diagram. The leaves of the tree are terminalsD, while all the other nodes are nonterminalsD.

  terminal. A symbol that only occurs on the right-hand side of a grammar ruleD; cannot be substituted. A sentenceD of a languageD consists of a sequence of only terminals.

  Concept How It Appears in Over the Rainbow

  Ambiguity A verse without bar symbol

  Abstract syntax Tree of measures and notes

  AlgorithmA The score in staff notation or tablature

  Compositionality Sound of the song is concatenation of the sounds of its measures

  ComputerA Judy Garland as a singer or musician

  Concrete syntax Staff notation; tablature

  ExecutionA Singing or playing

  Derivation Expanding melody into the score using the grammar rules

  Grammar The grammar for melodies

  Grammar rule

  Language All valid staff notations

  Nonterminal measure

  Parsing Identifying the structure given through verses, chorus, measures, etc.

  Semantic domain Sounds

  Semantics definition Mapping of syntax tree to sounds

  Sentence The song given in staff notation

  Sentential form

  Start symbol melody

  Syntax Rules for typesetting staff notation

  Syntax tree Tree of measures and notes

  Terminal

  E. Control Structures and Loops

  body (of a loop). A group of operations to be repeated by a loopE. Must modify the program state to allow the terminationE of the loop.

  conditional. A control structureE for deciding between the executionA of one of two groups of operations.

  control structure. A part of an algorithmA for organizing the order, application, and repetition of operations. The three major control structures are loopsE, conditionalsE, and recursionF.

  for loop. A loopE whose bodyE is executed a fixed number of times.

  halting problem. Will an algorithmA always terminateE for any given inputA?

  loop. A control structureE for repeating the bodyE of the loop. The number of repetitions is determined by the termination conditionE, which is checked after each executionA of the loop’s body and which depends on the program state that can be changed by the operations of the loop’s body. In general, it is not clear how many repetitions the loop generates and thus whether the loop terminates. Two major kinds of loops are the repeat loopE and the while loopE. For these loops the termination condition determines how often the body will be repeated, which is generally not known before executing the loop. In contrast, the number of repetitions of a for loopE is fixed at the beginning of the loop, which guarantees the terminationE of for loopsE.

  repeat loop. A loopE whose termination conditionE is checked always after the operations of the loop’s bodyE have been executed.

  termination. A property of an algorithmA or computationA that holds when the computation ends. The termination of an algorithmA cannot be determined automatically by another algorithm; it is an undecidableE problemA.

  termination condition. A condition that determines whether a loopE ends or continues to run.

  undecidability. A property of a problemA. A problem is undecidable if it cannot be solved by an algorithmA A famous undecidable problem is the halting problemE.

  while loop. A loopE whose termination conditionE is always checked before the operations of the loop’s bodyE are executed.

  Concept How It Appears in Groundhog Day

  Body (of a loop) Events that happen during Groundhog day

  Conditional Any decision taken by Phil Connors

  Control structure The Groundhog Day loop

  For loop The number of repetitions in the movie is fixed in the script

  Halting problem Will the Groundhog day loop ever come to an end?

  Loop The repeating Groundhog day

  Repeat loop The Groundhog Day loop

  Termination The happy ending

  Termination condition Is Phil Connors a good person?

  Undecidability Inability to judge a priori whether Groundhog Day will end

  While loop The Groundhog Day loop

  F. Recursion

  base case. The nonrecursive part of a recursive definitionF. When a recursive algorithmA reaches a base case, the recursionF will stop at that point. A base case is required, but not sufficient, for a recursion to terminateE.

  bounded recursion. A recursionF that terminatesE.

  descriptive recursion. When the definition of a concept contains a reference to itself, usually through the use of a name or symbol. Sometimes called self-reference.

  direct recursion. When the definition of a name or object contains a reference to itself.

  fixed point. A solution to a recursive equation.

  indirect recursion. When the definition of a name or object does not contain a reference to itself but rather contains another name that contains the reference.

  interpreter. A computerA that executesA an algorithmA using a stackB data typeB to keep track of recursiveF (and nonrecursive) calls and multiple copies of arguments that arise as a consequence of recursive callsF.

  paradox. A logical contradiction, which is caused by a descriptive recursionF that cannot be executed to yield a boundedF unfolded recursionF. A recursive equation describes a paradox if it doesn’t have a fixed pointF.

  recursion. Refers either to descriptive recursionF, unfolded recursionF, or the executionA of a recursive definitionF.

  recursive call. A call to an algorithmA from within its own definition (direct recursionF) or from the definition of another algorithm that it calls (indirect recursionF).

  recursive definition. When the definition of a name or object contains a reference to itself. In a recursive definition of an algorithmA the reference is also called a recursive callF.

  substitution. The process of replacing parametersA by concrete values. Replacing the call of an algorithmA by its definition while substituting the arguments for the parameters.

  trace. A sequence that captures the different states a computationA went through. Helpful in illustrating the executionA of an algorithmA that is given by a recursive definitionF.

  unbounded recursion. A recursionF that does not terminateE. This happens when the recursive definitionF lacks a base caseF or when the base case is not reached by the recursive callsF. Examples are never-ending songs, infinite listsB of numbers, or some nonterminating computationsA.

  unfolded recursion. When an artifact, typically a picture or text, contains a (sometimes scaled) copy of itself. Sometimes called self-similarity. Fractals and geometric patterns, such as Sierpinski triangles, are examples of unfolded recursion in pictures, and a never-ending song or poem is an example of unfolded recursion in text. Matryoshka dolls are an example of a recursive physical object.

  Concept How It Appears in Back to the Future

  Base case Marty saves Doc Brown in 1885

  Bounded recursion Time travel happens only a fixed number of times

  Descriptive recursion The description of time travel in ToDo or Goal

  Direct recursion Marty travels to 1885 after traveling to 1955

  Fixed poi
nt The actions taken by Marty and others are consistent

  Indirect recursion If Goal were split into two functions, say, Easy and Hard

  Interpreter The universe executing the time travel actions

  Paradox Jennifer sees her older/younger self

  Recursion Marty traveling into the past

  Recursive call The call ToDo(1885) in the definition of ToDo(1955)

  Recursive definition The definition of ToDo or Goal

  Substitution The sequence of actions obtained for a call of ToDo or Goal

  Trace The linear sequence of actions from Back to the Future

  Unbounded recursion If Marty never stopped traveling back in time

  Unfolded recursion The sequence of actions resulting from time travel

  G. Types and Abstraction

  abstract machine. A high-level description of a machine, often given as a mathematical model, that ignores details of actual machines and thus provides a unifying view on a large number of different but similar machines. The Turing MachineG is an example.

  abstraction. The process of ignoring the details in a description and summarizing it. Also the result of that process. To facilitate the use of an abstraction, it is given an interfaceG.

  axiom. A rule that is always true. A typing ruleG is an axiom if it has no premisesG.

  Church-Turing thesis. The claim that any algorithmA can be expressed as a programA for a Turing machineG or lambda calculusG. Is believed to be true by most computer scientists.

  conclusion. A part of a typing ruleG. The conclusion of a typing ruleG is true only if all its premisesG are true.

  data abstraction. When abstractionG is applied to representationA,B. Provides a common view on a number of different data. TypesG are a major form of data abstraction.

  dynamic type checking. Checking typesG during the executionA of an algorithmA.

  functional abstraction. When abstractionG is applied to computationA. Provides a common view on a number of different computations. Embodied in the concept of an algorithmA, which describes a class of similar computations.