C

| < Day Day Up > |

# 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

| < Day Day Up > |