by Martin Erwig
direct, 206, 220
indirect, 220, 224
linear, 236
nonlinear, 236
unbounded, 206, 219
unfolded, 214
see also bounded ↔ unbounded recursion; descriptive ↔ unfolded recursion; direct ↔ indirect recursion; divide-and-conquer; recursion ↔ loop; recursion examples
recursion ↔ loop, 185, 218–219
recursion examples
99 bottles, 204
Count, 211, 213, 215, 249
descendant, 205
drawing hands, 220
Even, 221
FindHomeFrom, 218
Goal, 210
GroundhogDay, 185, 218
Isort, 229, 233, 234
Matryoshka dolls, 204
Odd, 221
Ones, 220
print gallery, 220
Qsort, 236, 249
room with TV, 205, 228
Sierpinski triangles, 224
ToDo, 208, 231
see also algorithm, binary search; divide-and-conquer; recursion
recursive equation, 211, 221
recursive picture, 228
see also recursion examples, room with TV
recursive rule (grammar), 148
reduction, see problem reduction
repeat loop ↔ while loop, 183, 184
repeat/while loop ↔ for loop, 186
representation, 21, 22, 55
ambiguity, 54
layers of, 22, 53
music, 167
number, 3, 10, 50, 52, 53
transformation of, 33, 58
see also computation representation; problem representation; sign
representation level, see representation, layers of
resource requirements, see algorithm, resource requirements
result, see output
reuse, 107
rewriting, 229
RHS (right-hand side), 147
right-hand side, 147
Roman numerals, 50
rule (grammar), 147
rule (typing), 9, 245, 251
runtime, 31, 38, 276
constant, 67
exponential, 5, 120, 122, 124–126
linear, 40, 110
linearithmic, 110, 110, 305n6
logarithmic, 95
of loops, 185
quadratic, 41, 110
worst case, 39, 40
see also exponential ↔ non-exponential runtime; linear ↔ linearithmic ↔ quadratic runtime
runtime abstraction, 275–276
runtime complexity, see runtime
search
in a list, 84
see also dictionary, implementation
in a tree, see binary search; trie
key, 84, 85
search problem, see problem examples, searching
search space, 81, 84, 88
selection sort ↔ insertion sort, 107
self-application, 195
self-reference, 203, 205, 228, 228
self-replicating machines, 9
semantic domain, 164
semantics, see language; semantics
semiotics, 51
sentence, 142, 145
sentence structure, 142
sentential form, 147
see also sentence; grammar
sequential composition, 173, 179
set, 66, 67
difference, 71
intersection, 71
see also data type; dictionary
sign, 51–53, 55, 141
icon, 56
index, 56, 144
interpretation, 47, 56
meaning, 47
signified, 51, 55
signifier, 51, 55, 70, 89
symbol, 56
transitivity, 53
see also representation
signified (sign), 51, 55
signifier (sign), 51, 55, 70, 89
solution, see problem solving
sorting, 101
see also sorting algorithms
sorting algorithms
bucket sort, 111
counting sort, 113
insertion sort, 106, 106, 229, 230
mergesort, 111, 112
quicksort, 108, 109, 236
selection sort, 105, 105, 185
type of, 249
space complexity, see space requirements
space requirements, 38, 65
spaghetti code, 182, 209
spreadsheet, 6
stack, 62, 63, 72, 247
implementation by list, 73
used by interpreter, 231–235
see also data type; last in, first out
start symbol (grammar), 150
state, 191, 223
static ↔ dynamic type checking, 256–258
storage space, 32
linear, 42
substitution, 34, 147, 226–229, 230, 266
see also parameter
symbol (sign), 56
synonym, 54
syntax, 6, 145
abstract, 142, 151
concrete, 142, 151
see also grammar; parse tree
syntax tree, see abstract syntax tree; parse tree
terminal, 146, 147
termination, 178–179, 185, 187
termination condition, 178, 179, 183, 191–195, 309n6
see also loop, condition
textual language ↔ visual language, 181
time abstraction, see runtime abstraction
trace, 223, 230, 231
tree, 73
ancestor, 73
child, 74
descendant, 73
height, 95
internal node, 91
leaf, 74
node, 74
parent, 74
path, 92
root, 74
subtree, 91
see also data structure
trie, 97–99, 100
see also data structure
Turing machine, 278, 281
Turing test, 141
Turing, Alan, 194, 278
type, 9, 142, 243, 247, 274
algorithms, for, 247, 248, 253
see also data type
type checker, 246, 256
see also dynamic ↔ static type checking
type correctness, 246, 255
type error, 10, 244, 246, 255
type parameter, 249
type-directed programming, 254
typing rule, 9, 246, 251
unbounded ↔ bounded recursion, 219
uncomputable problem, see problem, undecidable
undecidable problem, see problem, undecidable
unfolded ↔ descriptive recursion, 214
unsolvable problem, see problem, undecidable use-mention distinction, 51
variable, 146, 177, 191
see also parameter
visual language ↔ textual language, 181
von Neumann, John, 111, 115, 306n6
way finding, see problem examples, path finding; algorithm examples, path finding
while loop ↔ repeat loop, 183, 184
worst-case complexity, see runtime, worst case
Zuse, Konrad, 303n6