A

| < Day Day Up > |

# Index

### A

AA-tree, 301
abelian group, 862
ABOVE, 942
above relation, 941
absent child, 1089
absolutely convergent series, 1059
absorption laws for sets, 1072
abstract problem, 972
acceptable pair of integers, 894
acceptance
by an algorithm, 976
by a finite automaton, 916
accepting state, 916
accounting method, 410- 412
for binary counters, 411- 412
for dynamic tables, 419
for stack operations, 410- 411, 412 ex.
Ackermann's function, 521
activity-selection problem, 371- 379
acyclic graph, 1082
relation to matroids, 403 pr.
add instruction, 22
addition
of binary integers, 21 ex.
of matrices, 728
modulo n (+n), 863
of polynomials, 822
additive group modulo n, 863
addressing, open, see open addressing
adjacency-list representation, 528
adjacency-matrix representation, 529
adjacent vertices, 1080
admissible edge, 681
admissible network, 681- 683
aggregate analysis, 406- 410
for binary counters, 408- 409
for breadth-first search, 534
for depth-first search, 542- 543
for Dijkstra's algorithm, 598
for disjoint-set data structures, 503- 504, 505 ex., 509 ex.
for dynamic tables, 418- 419
for Fibonacci heaps, 493 ex.
for Graham's scan, 954- 955
for shortest paths in a dag, 592
for stack operations, 406- 408
aggregate flow, 788
Akra-Bazzi method for solving a recurrence, 89- 90
AKS sorting network, 724
algorithm, 5
correctness of, 6
origin of word, 40
running time of, 23
as a technology, 12
Alice, 881
ALLOCATE-NODE, 442
ALLOCATE-OBJECT, 211
allocation of objects, 210- 212
all-pairs shortest paths, 581, 620- 642
in ∈-dense graphs, 641 pr.
Floyd-Warshall algorithm for, 629- 632
Johnson's algorithm for, 636- 640
by matrix multiplication, 622- 629
by repeated squaring, 625- 627
alphabet, 916, 975
α(n), 511
amortized analysis, 405- 429
accounting method of, 410- 412
aggregate analysis, 406- 410
for bit-reversal permutation, 425 pr.
for breadth-first search, 534
for depth-first search, 542- 543
for Dijkstra's algorithm, 598
for disjoint-set data structures, 503- 504, 505 ex., 509 ex., 512- 517, 518 ex.
for dynamic tables, 416- 425
for Fibonacci heaps, 479- 482, 487- 488, 491- 492, 493 ex.
for the generic push-relabel algorithm, 678- 679
for Graham's scan, 954- 955
for the Knuth-Morris-Pratt algorithm, 926- 927
for making binary search dynamic, 426 pr.
potential method of, 412- 416
for restructuring red-black trees, 428 pr.
for shortest paths in a dag, 592
for stacks on secondary storage, 452 pr.
for weight-balanced trees, 427 pr.
amortized cost
in the accounting method, 410
in aggregate analysis, 406
in the potential method, 413
analysis of algorithms, 21- 27
see also amortized analysis, probabilistic analysis
ancestor, 1087
least common, 521 pr.
AND function (^), 633, 987
AND gate, 987
and, in pseudocode, 20
antisymmetry, 1076
ANY-SEGMENTS-INTERSECT, 943
approximation
by least squares, 762- 765
of summation by integrals, 1067
approximation algorithm, 1022- 1054
for bin packing, 1049 pr.
for MAX-CNF satisfiability problem, 1043 ex.
for MAX-CUT problem, 1043 ex.
for the maximum-clique problem, 1050 pr.
for maximum matching, 1051 pr.
for MAX-3-CNF satisfiability, 1039- 1040
for minimum-weight vertex cover, 1040- 1043
for parallel-machine-scheduling problem, 1051 pr.
randomized, 1039
for the set-covering problem, 1033- 1038
for the subset-sum problem, 1043- 1049
for the traveling-salesman problem, 1027- 1033
for the vertex-cover problem, 1024- 1027
for the weighted set-covering problem, 1050 pr.
approximation ratio, 1022, 1039
approximation scheme, 1023
APPROX-MIN-WEIGHT-VC, 1041
APPROX-SUBSET-SUM, 1046
APPROX-TSP-TOUR, 1028
APPROX-VERTEX-COVER, 1025
arbitrage, 615 pr.
arc, see edge
argument of a function, 1078
arithmetic, modular, 51- 52, 862- 869
arithmetic instructions, 22
arithmetic series, 1059
arithmetic with infinities, 587
arm, 435
array, 19
Monge, 88 pr.
articulation point, 558 pr.
assembly-line scheduling, 324- 331
assignment
multiple, 19
satisfying, 988, 996
truth, 988, 996
associative laws for sets, 1072
associative operation, 862
asymptotically larger, 49
asymptotically nonnegative, 42
asymptotically positive, 42
asymptotically smaller, 49
asymptotically tight bound, 42
asymptotic efficiency, 41
asymptotic lower bound, 45
asymptotic notation, 41- 50, 59 pr.
and graph algorithms, 526
and linearity of summations, 1059
asymptotic upper bound, 44
attribute of an object, 20
augmenting data structures, 302- 318
augmenting path, 654, 696 pr.
authentication, 251 pr.
automaton
finite, 916
string-matching, 917- 922
auxiliary hash function, 239
auxiliary linear program, 811
average-case running time, 26
AVL-INSERT, 296 pr.
AVL tree, 296 pr.
axioms, for probability, 1100

| < Day Day Up > |