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

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