Index
G c O(F), 285
Ordering Three Values 1, 301
binary predicate, 135
P(n, r), 436
Ordering Three Values II, 302
binary function, 223
R*, 175
Ordering Three Values III, 303
binary relation, 159, 222
R+, 175
Perfect Squares, 58
composition, 165
k to 1, 254
Selection Sort, 314
binary search, 81, 87, 568
n-tuples, 495
Square Root I, 59
binary search tree, 382
i.i.d., 534
Square Root II, 61
binary tree, 381
1-1 correspondence, 234
TSP, 422
binomial
3-satisfiability problem, 129
UNION-FIND, 188
coefficients, 459
algorithm, 56, 283, 317, 484, 579
distribution, 522
A-V-L trees, 384
extends, 320
Binomial Theorem, 459
above, 197
polynomial time, 309
bipartite
absorption law, 19
halts, 283
graph, 335
Absorption Law for Join, 29
stops, 283
bipartite graph
Absorption Law for Meet, 29
terminates, 283
directed, 393
accepted, 591, 592
alphabet, 587, 591
bipartition, 335
accepting state, 591
alphabetic variant, 120
Birthday Problem, 487
acyclic graph, 341
alphabetical ordering, 194
bit, 514
Addition Principle, 426, 427
ancestor, 379
bit operations
additive principle of disjoint events,
antisymmetric, 170
COMP, 22
485
intersection, 17
DIFF, 22
adjacency list, 347
arrangements, 437
INTER, 22
adjacency matrix, 346
associative law, 108
UNION, 22
adjacent, 334, 393
union, 16
bits, 498
adjacent edges, 334
Associative Law for Join, 29
boolean
algebraic number, 272
Associative Law for Meet, 29
algebra, 30
algebraic proof, 457
asymptotically dominates, 285, 288
function, 227
Algorithm
atomic formula, 135
boundary value, 554, 562
Binary Search, 78, 569
attribute, 203
breadth first search, 358
Bubble Sort 1, 305
attribute values, 203
tree, 358
Bubble Sort II, 307
autark, 420
bridge, 544
Compute Powers, 73
axiom of choice, 266
computing a' recursively, 583
C(n, r), 440
computing Fn, 88, 583
back substitution, 552, 555
Cantor's Second Diagonal Argument,
Detecting Order for Three Values,
base case, 94, 589
271
300
Base step, 48
cardinality, 34, 265
Factor Positive Integer, 76
Bayes' Rule, 514
Cartesian product, 28
Finding a Minimal Element, 198
below, 197
ceiling function, 220, 240
Join Two Relations, 210
Bernoulli
certificate, 310
Largest Odd Divisor, 75
process, 498
chance, 475
linear search, 584
trial process, 498
characteristic equation, 563
merge sort, 571
biconditional, 91
child, 379
NegSelfRef, 319
bijective, 234
Church's thesis, 316
595
G c O(F), 285
Ordering Three Values 1, 301
binary predicate, 135
P(n, r), 436
Ordering Three Values II, 302
binary function, 223
R*, 175
Ordering Three Values III, 303
binary relation, 159, 222
R+, 175
Perfect Squares, 58
composition, 165
k to 1, 254
Selection Sort, 314
binary search, 81, 87, 568
n-tuples, 495
Square Root I, 59
binary search tree, 382
i.i.d., 534
Square Root II, 61
binary tree, 381
1-1 correspondence, 234
TSP, 422
binomial
3-satisfiability problem, 129
UNION-FIND, 188
coefficients, 459
algorithm, 56, 283, 317, 484, 579
distribution, 522
A-V-L trees, 384
extends, 320
Binomial Theorem, 459
above, 197
polynomial time, 309
bipartite
absorption law, 19
halts, 283
graph, 335
Absorption Law for Join, 29
stops, 283
bipartite graph
Absorption Law for Meet, 29
terminates, 283
directed, 393
accepted, 591, 592
alphabet, 587, 591
bipartition, 335
accepting state, 591
alphabetic variant, 120
Birthday Problem, 487
acyclic graph, 341
alphabetical ordering, 194
bit, 514
Addition Principle, 426, 427
ancestor, 379
bit operations
additive principle of disjoint events,
antisymmetric, 170
COMP, 22
485
intersection, 17
DIFF, 22
adjacency list, 347
arrangements, 437
INTER, 22
adjacency matrix, 346
associative law, 108
UNION, 22
adjacent, 334, 393
union, 16
bits, 498
adjacent edges, 334
Associative Law for Join, 29
boolean
algebraic number, 272
Associative Law for Meet, 29
algebra, 30
algebraic proof, 457
asymptotically dominates, 285, 288
function, 227
Algorithm
atomic formula, 135
boundary value, 554, 562
Binary Search, 78, 569
attribute, 203
breadth first search, 358
Bubble Sort 1, 305
attribute values, 203
tree, 358
Bubble Sort II, 307
autark, 420
bridge, 544
Compute Powers, 73
axiom of choice, 266
computing a' recursively, 583
C(n, r), 440
computing Fn, 88, 583
back substitution, 552, 555
Cantor's Second Diagonal Argument,
Detecting Order for Three Values,
base case, 94, 589
271
300
Base step, 48
cardinality, 34, 265
Factor Positive Integer, 76
Bayes' Rule, 514
Cartesian product, 28
Finding a Minimal Element, 198
below, 197
ceiling function, 220, 240
Join Two Relations, 210
Bernoulli
certificate, 310
Largest Odd Divisor, 75
process, 498
chance, 475
linear search, 584
trial process, 498
characteristic equation, 563
merge sort, 571
biconditional, 91
child, 379
NegSelfRef, 319
bijective, 234
Church's thesis, 316
595