Index

C

cache, 22

cache-oblivious, 454

call

a subroutine, 22, 23 n.

by value, 20

cancellation lemma, 831

cancellation of flow, 646

canonical form for task scheduling, 399

capacity

of a cut, 655

of an edge, 644

residual, 651, 654

capacity constraint, 644

cardinality of a set (||), 1073

Carmichael number, 890, 896 ex.

Cartesian product (×), 1074

Cartesian sum, 830 ex.

cascading cut, 490

CASCADING-CUT, 490

Catalan numbers, 271 pr., 333

ceiling function (⌈;⌉;), 51

in master theorem, 81–84

ceiling instruction, 22

certain event, 1100

certificate

in a cryptosystem, 886

for verification algorithms, 980

CHAINED-HASH-DELETE, 226

CHAINED-HASH-INSERT, 226

CHAINED-HASH-SEARCH, 226

chaining, 225–228, 250 pr.

chain of a convex hull, 955

changing

a key in a Fibonacci heap, 497 pr.

variables in the substitution method, 66

character code, 385

child, 1087, 1089

child list in a Fibonacci heap, 477

Chinese remainder theorem, 873–876

chirp transform, 838 ex.

choose , 1096

chord, 308 ex.

ciphertext, 883

circuit

boolean combinational, 988

for Fast Fourier Transform, 842–843

CIRCUIT-SAT, 989

circuit satisfiability, 987–994

circular, doubly linked list with a sentinel, 206

circular linked list, 204

see also linked list

class

complexity, 977

equivalence, 1075

classification of edges

in breadth-first search, 558 pr.

in depth-first search, 546–547, 548 ex.

clause, 999

clean sequence, 713

clique, 1003

CLIQUE, 1003

clique problem, 1003–1006

approximation algorithm for, 1050 pr.

closed interval, 311

closed semiring, 642

closest pair, finding, 957–962

closest-point heuristic, 1033 ex.

closure

group property, 862

of a language, 976

operator (*), 976

transitive, see transitive closure

clustering, 239–240

CNF (conjunctive normal form), 967, 999

CNF satisfiability, 1043 ex.

code, 385

Huffman, 385–393

codomain, 1077

coefficient

binomial, 1096

of a polynomial, 52, 822

in slack form, 783

coefficient representation, 824

and fast multiplication, 827–829

cofactor, 732

coin changing, 402 pr.

collinearity, 935

collision, 224

resolution by chaining, 225–228

resolution by open addressing, 237–245

coloring, 1019 pr., 1091 pr.

color of a red-black-tree node, 273

column rank, 731

column vector, 726

combination, 1096

combinational circuit, 988

combinational element, 987

comment in pseudocode (▻), 19

commodity, 788

common divisor, 852

greatest, see greatest common divisor

common multiple, 861 ex.

common subexpression, 839

common subsequence, 351

longest, 350–356, 369

commutative laws for sets, 1071

commutativity under an operator, 862

COMPACTIFY-LIST, 213 ex.

compact list, 218 pr.

COMPACT-LIST-SEARCH, 218 pr.

COMPACT-LIST-SEARCH', 219 pr.

comparable line segments, 941

comparator, 705

comparison network, 704–709

comparison sort, 165

and binary search trees, 256 ex.

and mergeable heaps, 489 ex.

randomized, 178 pr.

and selection, 192

compatible activities, 371

compatible matrices, 332, 729

complement

of an event, 1101

of a graph, 1007

of a language, 976

Schur, 748, 761

of a set, 1072

complementary slackness, 818 pr.

complete graph, 1083

complete k-ary tree, 1090

see also heap

completeness of a language, 994 ex.

completion time, 402 pr., 1051 pr.

complexity class, 977

co-NP, 982

NP, 967, 981

NPC, 968, 986

P, 967, 973

complexity measure, 977

complex numbers, multiplication of, 741 ex.

complex root of unity, 830

interpolation at, 836–837

component

biconnected, 558 pr.

connected, 1082

strongly connected, 1082

component graph, 554

composite number, 851

witness to, 890

computational geometry, 933–965

computational problem, 5–6

COMPUTE-PREFIX-FUNCTION, 926

COMPUTE-TRANSITION-FUNCTION, 922

concatenation

of languages, 976

of strings, 907

concrete problem, 973

conditional branch instruction, 22

conditional independence, 1106 ex.

conditional probability, 1103–1104

configuration, 991

conjugate transpose, 759 ex.

conjunctive normal form, 967, 999

connected component, 1082

identified using depth-first search, 549 ex.

identified using disjoint-set data structures, 499–501

CONNECTED-COMPONENTS, 500

connected graph, 1082

connective, 996

co-NP, 982

conservation of flow, 644

consistency of literals, 1004

CONSOLIDATE, 486

consolidating a Fibonacci-heap root list, 483

constraint, 777

difference, 602

equality, 606 ex., 778, 780

inequality, 778, 780

linear, 772

nonnegativity, 777, 779

tight, 791

violation of, 791

constraint graph, 603–605

contain, in a path, 1081

continuous uniform probability distribution, 1102

contraction

of a dynamic table, 420–422

of a matroid, 397

of an undirected graph by an edge, 1084

control instructions, 22

convergence property, 587, 609

convergent series, 1059

convex combination of points, 934

convex function, 1109

convex hull, 947–957, 964 pr.

convex layers, 962 pr.

convex polygon, 939 ex.

convex set, 650 ex.

convolution (⊗), 825

convolution theorem, 837

copy instruction, 22

correctness of an algorithm, 6

countably infinite set, 1073

counter, see binary counter

counting, 1094–1100

probabilistic, 118 pr.

counting sort, 168–170

in radix sort, 172

COUNTING-SORT, 168

coupon collector's problem, 110

cover

path, 692 pr.

by a subset, 1034

vertex, 1006, 1024, 1040–1043

covertical, 942

credit, 410

critical edge, 662

critical path, 594

cross edge, 546

crossing a cut, 563

cross product (×), 934

cryptosystem, 881–887

cubic spline, 767 pr.

curve fitting, 762–765

cut

cascading, 490

of a flow network, 654–657

of an undirected graph, 563

weight of, 1043 ex.

CUT, 489

cutting, in a Fibonacci heap, 490

cycle of a graph, 1081–1082

hamiltonian, 967, 979

minimum mean-weight, 617 pr.

negative-weight, see negative-weight cycle

and shortest paths, 583

cyclic group, 877

cyclic rotation, 930 ex.

cycling, of simplex algorithm, 802

cylinder, 435