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