4. If you know the difference between “countably many” and “uncountably many” the number of decidable problems is countable, whereas the number of undecidable problems is uncountable.
Chapter 12 A Stitch in Time Computes Fine
1. Incidentally, Carl Sagan thought that Back to the Future II was the best movie ever made based on the science of time travel; in “Q&A Commentary with Robert Zemeckis and Bob Gale,” Back to the Future Part II, Blu-Ray (2010).
2. Remember that the semicolon is the control structure that sequentially composes steps of an algorithm.
3. The situation is a bit more complicated than this, but the analogy is still valid.
4. The recursive description is longer because the name of the algorithm has to be mentioned explicitly.
5. One can also distinguish between generative and structural recursion, but that distinction is not so important for the fundamental understanding of the concept of recursion itself. Moreover, one can distinguish between linear and nonlinear recursion (see chapter 13).
6. See en.wikipedia.org/wiki/Drawing_Hands and en.wikipedia.org/wiki/Print_Gallery_(M. _C._Escher).
7. Only when the algorithms are applied to nonnegative numbers.
8. From David Hunter, Essentials of Discrete Mathematics (2011).
State of the Art
1. Note that it is not simply the collection of results that define an algorithm, because different algorithms for solving the same problem are distinguished by how they solve the problem.
Chapter 13 A Matter of Interpretation
1. This is way of passing arguments to parameters is called call-by-value.
2. In this example, the parameter values are actually not needed anymore, and the computation of Isort is also completed.
3. Maybe that’s because young Biff is not aware that the old man who gives him the sports almanac is his older self.
4. In practice, one can stop the recursion with lists of length 1, which are sorted and can also be returned unchanged.
Chapter 14 The Magical Type
1. If the alarm clock uses a 12-hour time format, it requires an additional a.m./p.m. indicator.
2. Types that can be described in this way are called polymorphic, since they can have many different forms. Since all the different forms can be described using one parameter, this kind of polymorphism is called parametric polymorphism.
3. However, the power of typing rules is limited. They cannot, for example, guarantee the termination of algorithms.
4. This all depends on the context. Usually, one would also say that it doesn’t make sense to multiply the height of a person with itself, but the square of a person’s height is actually used to divide the weight of a person to compute the so-called body-mass index.
5. Published in the United Kingdom as Harry Potter and the Philosopher’s Stone.
Chapter 15 A Bird’s Eye View: Abstracting from Details
1. The word abstraction has its origin in Latin where the verb abstrahere means “to draw away.”
2. This definition could be further extended to work with lists of arbitrarily many protagonists. However, such a definition would be a bit more complicated.
3. For brevity, rules for expanding the nonterminals protagonist and challenge have been omitted.
4. The conic visualization of an abstraction is itself an abstraction with the abstract concept at the top and the concepts abstracted from at the bottom.
5. Ignoring here the fact that a runner will eventually get tired, which places a natural limit on the length of runs.
6. In this context, the word algorithm refers more narrowly to methods for computing mathematical functions, which does not includes, for example, recipes.
Index
Page numbers in italics refer to figures and tables.
abbreviation, 52, 53, 56
abstract machine, 278, 279
abstract syntax, 142, 151
abstract syntax tree, 151
abstract syntax tree ↔ parse tree, 151, 153, 153
abstraction, 10, 261, 264–265, 267
algorithm, 10, 272, 271–273
application of, 266
computation, of, 271, 272
computers, of, 279, 281
data, 273, 281
design of, 268–271
examples of, 10, 264
functional, 273, 281
hierarchy, 281
instance of, 265, 267
interface, 265, 267
machines, of, 278, 279
mechanisms, 270
representation, of, 272
representations as, 273–275
runtime, of, 275–276, 277
type, 272
access pattern, see data access pattern
algorithm, 17, 25, 281, 311n6
approximation, 120, 129, 257
complexity, see runtime
correctness, 27–29
defining characteristics, 26–27
desirable properties, 27–29
divide-and-conquer, 103, 112, 236
effect of, 25
execution, 18, 19, 35, 36, 166
see also computation
generate-and-test, 123
greedy, 130
hard-wired, 36
input, see input
linear, see runtime, linear
optimal, 114
output, see output
quadratic, see runtime, quadratic
recursive, 8, 75, 113
resource requirements, 32, 38
runtime of, see runtime
step, 38
termination, see loop, termination, 29
see also algorithm examples; Church-Turing thesis; program; recursion examples
algorithm ↔ computation, 26, 35, 38, 177
algorithm examples
binary search, see binary search
data compression, 3
Halts, 194, 196
Loop, 194, 195
making coffee, 34
page rank, 3
path finding, 25, 218
see also problem examples, path finding
recipe, 2
Selfie, 196
set intersection, 71
sorting, see sorting algorithms
square root, 1, 2
tree traversal, 73, 76
see also algorithm
ambiguity, see language, ambiguity; representation, ambiguity
ambiguity ↔ nondeterminism, 162
ancestor (tree), 73
application typing rule, 251
approximation algorithm, 120, 129, 257
array, 62, 67, 69, 86, 113
index, 67, 86
notebook analogy, 67
see also data structure
array ↔ list, 67, 69, 90
artificial intelligence, 141
axiom (typing rule), 251
Babbage, Charles, 303n6
barber paradox, 197
Bertillon, Alphonse, 57
binary numbers, 50, 53, 304n6
binary representation, see binary numbers
binary search, 82, 203
property, 92
tree, 92, 91–96
tree, balanced, 95, 97
see also tree
binding, 233
boundary (search), 85, 91, 111
bounded ↔ unbounded recursion, 219
bucket sort, 272
Church, Alonzo, 280
Church-Turing thesis, 281
collection, 61, 63
ordering of elements, 72
complexity
algorithmic, see runtime; space requirements
problem, see lower bound
compositionality, 159, 165
computation, 18–20, 22, 23, 144
description of, see algorithm
essence of, 23, 25
limits of, see computer science, principal limitations
resources, 1, 38
role in society, 1–10
step, 21, 38
stuck, 28, 254
with signs, 57, 58
see also algorithm, execution; representation, transformation of
computation ↔ algorithm, 26, 35, 38, 177
computation ↔ problem solving, 23, 24
computation examples, see algorithm examples
computation representation, 22, 52
see also representation
computer, 31, 36
requirements, 37
universal, 36
see also computer examples
computer examples
alarm clock, 36
difference engine, 303n6
human, 36, 139, 144, 158
laptop, 36
pocket calculator, 36
ribosome, 37
smart phone, 36
Z1, 303n6
see also computer
computer science
essence of, 262, 264, 282–283
objectives, 18, 32, 122, 129, 140, 269
principal limitations, 103, 198
science of problem solving, 4, 18, 282
computing, see computation
conclusion (typing rule), 251
concrete syntax, 142, 151
condition, 178, 185
conditional, 179
control structure, 7, 173, 179
conditional, 179
loop, see loop
sequential composition, 173, 179
see also recursion
Cook, Stephen, 128
correctness, 27–29, 193, 246, 255
data abstraction, 273, 281
data access pattern, 61, 63
data structure, 62, 64, 69
recursive, 91
data structure ↔ data type, 64, 66, 275
data type, 61, 63, 66, 69, 275
data type ↔ data structure, 64, 66, 275
de Saussure, Ferdinand, 51
decidability, see problem, unsolvable
decimal numbers, 50, 53
decimal representation, see decimal numbers
decomposition, see problem decomposition
denotational semantics, 164, 165–167
derivation (grammar), 150
descendant (recursion example), 205
descendant (tree), 73
descriptive ↔ unfolded recursion, 214
dictionary, 70, 90
implementation, 68, 69, 90
key, 70
see also data type; set
direct ↔ indirect recursion, 220
distributed computing, 47, 182
divide-and-conquer, 103, 113, 236
see also recursion
Droste effect, 9
dynamic ↔ static type checking, 256–258
efficiency, see space requirements; runtime
encryption, see public key encryption, 5, 131
enerate-and-test, 123
Escher, M. C, 162, 220
execution, see algorithm, execution
execution time, see runtime
exponential ↔ nonexponential runtime, 125
exponential algorithm, see exponential runtime
exponential growth, see exponential runtime
exponential runtime, 5, 120, 122, 124–126
FIFO (first in, first out), 72, 247
first come, first serve, 61, 72
first in, first out, 72, 247
fixed point, 215–217
flowchart, 180, 181, 183, 184
for loop, 185
for loop ↔ repeat/while loop, 186
fractals, 9
Frege, Gottlob, 165
functional abstraction, 273, 281
Gödel, Kurt, 128
Google, 3, 5, 81
grammar, 145
derivation, 150
nonterminal, 146, 147
recursive rule, 148
rule, 147
sentential form, 147
start symbol, 150
terminal, 146, 147
see also language; syntax
grandfather paradox, 214
greedy algorithm, 130
halting problem, 189, 194, 257
unsolvability, 194–197, 278
HIFO (highest in, first out), 73
highest in, first out, 73
Hindu-Arabic numerals, 3, 50
histogram, 90, 102
Hoare, Tony, 108
homonym, 54
HTML (hypertext markup language), 6, 151
hypertext markup language, 6, 151
icon (sign), 56
index
array, 67, 86
sign, 56, 144
indirect ↔ direct recursion, 220
input, 34, 246, 247, 252
see also parameter; substitution; type
insertion sort ↔ selection sort, 107
interface, 262
internet search, 5
interpreter, 166, 225, 231
trace, 232, 234
intractable problem, 4, 120, 126–129
intrinsic problem complexity, see lower bound
iteration, see loop, iteration
JavaScript, 6, 151
jump instruction, 209
key
dictionary, 70
private, 131
public, 131
search, 84, 85
lambda calculus, 280, 281
language, 5, 139, 141
ambiguity, 5, 145, 161, 159–163
see also ambiguity ↔ non-determinism
compositionality, 165
grammar, see grammar
meaning, see language, semantics
semantics, 157, 164, 163–165
sentence, 142, 145
structure, 139
syntax, see syntax
translation, 167, 278, 281
last in, first out, 73, 247
lazy evaluation, 117
see also precomputation
LIFO (last in, first out), 73, 247
linear ↔ linearithmic ↔ quadratic runtime, 110
linear recursion, 236
linear runtime, 40, 110
linear storage space, 42
linearithmic runtime, 110, 110, 305n6
list, 62, 64, 69
finding element in, 66
infinite, 220
notation, 65
ring-binder analogy, 66
see also data structure
list ↔ array, 67, 69, 90
logical paradox, 197, 214
loop, 7, 173, 176
body, 176, 179
condition, 178, 185
iteration, 176, 183, 185, 190
termination, 178–179, 185, 187
unfolding, 192, 192
see also control structure
loop ↔ recursion, 185, 218–219
lower bound, 103, 115, 128
machine abstraction, 278, 279
Mars Climate Orbiter, 10, 55
meaning (language), see language, semantics
meaning (sign), 47
mergesort, 272
method (for solving problems), see algorithm
music notation, 143–145
mutual recursion, see recursion, indirect
NASA, 10, 55
Necker cube, 162
nondeterminism, 161, 307n6
see also ambiguity ↔ non-determinism
nondeterminism ↔ ambiguity, 162
nonlinear recursion, 236
nonterminal, 146, 147
nontermination, 204
see also loop, termination
NP-complete problem, 126–129
number representation, see representation, number
order, see collection, ordering of elements
output, 26, 247, 252
see also type
P = NP problem, 122, 128, 307n6
paradox
barber, 197
grandfather, 214
parallel computing, 182, 236
parallelism, 182
parameter, 31, 34–35, 261, 265
see also input; subst
itution
parameter binding, 233
parse tree, 151
parse tree ↔ abstract syntax tree, 151, 153, 153
parsing, 153, 154
partition (of search space), 81, 85
pattern matching, 211, 270
Peirce, Charles Sanders, 56
Penrose triangle, 162
pivot element, 108, 111
pointer
between list elements, 65
to input, 35
policy, see data access pattern
precompilation, 102, 116
see also lazy evaluation
predicate, 71
prefix tree, 99
see also trie
premise (typing rule), 251
preorder traversal, 76
see also algorithm examples, tree traversal
pretty printing, 154, 154
priority queue, 61, 72
see also data type; highest in, first out
problem, 17
class, 26, 303n6
intractable, 4, 120, 126–129
intrinsic complexity, see lower bound
NP-complete, 126–129
P = NP, 122, 128, 307n6
uncomputable, 198
undecidable, 198, 257
see also halting problem
see also problem examples
problem complexity, see lower bound
problem decomposition, 17, 21, 103, 108, 111
see also divide-and-conquer
problem examples
finding home, 20, 22
getting up, 17
halting problem, see halting problem
knapsack, 127
path finding, 20, 88
searching, 5, 82, 83, 87
see also binary search
sorting, see sorting
traveling salesman, 5, 127
weighing, 123
see also algorithm examples; problem
problem reduction, 128
problem representation, 22, 52
see also representation
problem simplification, see problem decomposition
problem solving, 4, 19, 103
problem solving ↔ computation, 23, 24
program, 37
see also algorithm
programming language, 37, 279
public key encryption, 5, 131
quadratic runtime, 41, 110
queue, 4, 61, 72, 247
implementation by list, 73
see also data type; first in, first out
recursion, 8, 184, 203
base case, 220
bounded, 219
descriptive, 203, 213, 228