286 INDEX
Average-case analysis(continued)
of Quicksort, 91-93
for sequential search, 44-45
B
Backpack approximation, 236
Backpack problem, 222
Bellman, Richard, 252
Best-case analysis, 11-12
of bubble sort, 64
Biconnected components
algorithm, 144, 168-171
Big oh, 22, 23
Big omega, 22
Big theta, 23
Binary files, 122
Binary search, 42, 46-51
average-case analysis for, 49-51
Sherwood version of, 250
worst-case analysis for, 48-49
Binary trees, 15, 27, 29, 49, 77
Binomial coefficients, 254
Bin packing, 221-222
approximations, 235-236
Birthday example, 243-244
Block reads, 100
Boolean expressions, 7
Boolean variable problem, 218
Boyer-Moore algorithm, 128-135, 273
analysis of, 135
jump array, 132-134
match algorithm, 129-132
Breadth-first traversals, 151-153, 273
Bubble sort, 58, 63-66, 89
average-case analysis of, 65-66
best-case analysis of, 64
study suggestion results for, 266
worst-case analysis of, 64-65
bucketNumber, 7 4
“Buckets”
in radix sort, 73, 76
Buffon’s needle, 241-242C
C, 7
C++, 7
Cases
types of, 11-12
Character strings, 122
Chess
eight queens problem, 247-249
Children
in heapsort, 77, 78
Circle
inscribed within square, 241
Classes. See NP class; P class
CNF. See Conjunctive normal form
CNF-satisfiability problem, 219
Coefficients
preprocessing, 108-111
Coloring, graph, 228-229
Columns
and Gauss-Jordan method, 117, 118
in matrix, 112, 113
CombineBuckets function, 74
CombineSolutions function, 25
Common model, 185
Compare function, 47n2
Comparison operators, 10-11