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