B

| < Day Day Up > |

# Index

### B

back edge, 546, 550
back substitution, 745
bad guy, 539 ex.
BAD-SET-COVER-INSTANCE, 1038 ex.
BALANCE, 296 pr.
balanced search tree
AA-trees, 301
AVL trees, 296 pr.
B-trees, 434– 454
k-neighbor trees, 301
red-black trees, 273– 301
scapegoat trees, 301
splay trees, 301, 432
treaps, 296 pr.
2-3-4 trees, 439, 453 pr.
2-3 trees, 300, 454
weight-balanced trees, 301, 427 pr.
balls and bins, 109– 110, 1125 pr.
base, 350
base-a pseudoprime, 889
base case, 64
basic feasible solution, 792
basic solution, 792
basic variable, 782
basis function, 762
Batcher's odd-even merging network, 721 pr.
Bayes's theorem, 1104
BELLMAN-FORD, 588
Bellman-Ford algorithm, 588– 592
for all-pairs shortest paths, 620, 639
in Johnson's algorithm, 639
and objective functions, 606– 607 ex.
to solve systems of difference constraints, 605
Yen's improvement to, 614 pr.
BELOW, 942
Bernoulli trial, 1112
and balls and bins, 109– 110
and streaks, 110– 114
best-case running time, 27 ex., 46
BFS, 532
BIASED-RANDOM, 94 ex.
biconnected component, 558 pr.
big-oh notation, 43 fig., 44– 45
big-omega notation, 43 fig., 45– 46
bijective function, 1079
binary character code, 385
binary counter
analyzed by accounting method, 411– 412
analyzed by aggregate analysis, 408– 409
analyzed by potential method, 414– 415
and binomial heaps, 472 ex.
bit-reversed, 425 pr.
binary entropy function, 1098
binary gcd algorithm, 902 pr.
binary heap, see heap
binary relation, 1075
binary search, 37 ex.
with fast insertion, 426 pr.
in insertion sort, 37 ex.
in searching B-trees, 449 ex.
binary search tree, 253– 272
AA-trees, 301
AVL trees, 296 pr.
deletion from, 262– 263
with equal keys, 268 pr.
insertion into, 261
k-neighbor trees, 301
maximum key of, 258
minimum key of, 258
optimal, 356– 363, 369
predecessor in, 258– 259
querying, 256– 261
randomly built, 265– 268, 270 pr.
scapegoat trees, 301
searching, 256– 258
for sorting, 264 ex.
splay trees, 301
successor in, 258– 259
and treaps, 296 pr.
weight-balanced trees, 301
see also red-black tree
binary-search-tree property, 254
vs. min-heap property, 256 ex.
binary tree, 1088
full, 1089
number of different ones, 271 pr.
representation of, 214
see also binary search tree
binomial coefficient, 1096– 1098
binomial distribution, 1113– 1116
and balls and bins, 109
maximum value of, 1117 ex.
tails of, 1118– 1125
binomial expansion, 1096
binomial heap, 455– 475
and binary counter and binary addition, 472 ex.
creating, 461
decreasing a key in, 470
deletion from, 470– 471
extracting the minimum key from, 468– 469
insertion into, 468
minimum key of, 462
in minimum-spanning-tree algorithm, 474 pr.
properties of, 459
running times of operations on, 456 fig.
uniting, 462– 468
BINOMIAL-HEAP-DECREASE-KEY, 470
BINOMIAL-HEAP-DELETE, 470
BINOMIAL-HEAP-EXTRACT-MIN, 468
BINOMIAL-HEAP-INSERT, 468
BINOMIAL-HEAP-MERGE, 464
BINOMIAL-HEAP-MINIMUM, 462
BINOMIAL-HEAP-UNION, 463
BINOMIAL-LINK, 462
binomial tree, 457– 459
unordered, 479
bin packing, 1049 pr.
bipartite graph, 1083
corresponding flow network of, 665
d-regular, 669 ex.
and hypergraphs, 1084 ex.
bipartite matching, 497, 664– 669
Hopcroft-Karp algorithm for, 696 pr.
birthday paradox, 106– 109
biscuit to be kept out of basket, 646
bisection of a tree, 1092 pr.
bitonic euclidean traveling-salesman problem, 364 pr.
bitonic sequence, 712
and shortest paths, 618 pr.
BITONIC-SORTER, 715
bitonic sorting network, 712– 716
bitonic tour, 364 pr.
bit operation, 850
in Euclid's algorithm, 902 pr.
bit-reversal permutation, 425 pr., 841
BIT-REVERSE-COPY, 842
bit-reversed binary counter, 425 pr.
BIT-REVERSED-INCREMENT, 425 pr.
bit vector, 222 ex.
black-height, 274
black vertex, 531, 540
blocking flow, 697
block structure in pseudocode, 19
Bob, 881
Boole's inequality, 1105 ex.
boolean combinational circuit, 988
boolean combinational element, 987
boolean connective, 996
boolean formula, 967, 983 ex., 996, 1002 ex.
boolean function, 1098 ex.
boolean matrix multiplication
and transitive closure, 759 ex.
Boruvka's algorithm, 578
bottleneck spanning tree, 577 pr.
bottleneck traveling-salesman problem, 1033 ex.
bottom of a stack, 200
bound
asymptotically tight, 42
asymptotic lower, 45
asymptotic upper, 44
on binomial coefficients, 1097– 1098
on binomial distributions, 1116
polylogarithmic, 54
on the tails of a binomial distribution, 1118– 1125
boundary condition, 63– 64
boundary of a polygon, 939 ex.
bounding a summation, 1062– 1069
box, nesting, 615 pr.
B+-tree, 438
branching factor, in B-trees, 437
branch instructions, 22
breadth-first search, 531– 539
and shortest paths, 534– 537, 581
similarity to Dijkstra's algorithm, 599, 600 ex.
breadth-first tree, 532, 538
bridge, 558 pr.
B*-tree, 439
B-tree, 434– 454
creating, 442
deletion from, 449– 452
full node in, 439
height of, 439– 440
insertion into, 443– 447
minimum degree of, 439
minimum key of, 447 ex.
properties of, 438– 441
searching, 441– 442
splitting a node in, 443– 445
2-3-4 trees, 439
B-TREE-CREATE, 442
B-TREE-DELETE, 449
B-TREE-INSERT, 445
B-TREE-INSERT-NONFULL, 446
B-TREE-SEARCH, 442, 449 ex.
B-TREE-SPLIT-CHILD, 444
BUBBLESORT, 38 pr.
bucket, 174
bucket sort, 174– 177
BUCKET-SORT, 174
BUILD-MAX-HEAP, 133
BUILD-MAX-HEAP', 142 pr.
BUILD-MIN-HEAP, 135
butterfly operation, 839

| < Day Day Up > |