Index

R

R (set of real numbers), 1070

Rabin-Karp algorithm, 911-916

RABIN-KARP-MATCHER, 914

radix sort, 170-173

compared to quicksort, 173

RADIX-SORT, 172

radix tree, 269 pr.

RAM, see random-access machine RANDOM, 94, 94 ex.

random-access machine, 21-22

vs. comparison networks, 704

randomized algorithm, 93-94, 99-105

and average inputs, 26

comparison sort, 178 pr.

for the hiring problem, 100

for insertion into a binary search tree with equal keys, 268 pr.

for MAX-3-CNF satisfiability, 1039-1040

Miller-Rabin primality test, 890-896

for partitioning, 154, 159 ex., 160 pr., 162 pr.

for permuting an array, 101-104

Pollard's rho heuristic, 897-901, 901 ex.

and probabilistic analysis, 99-101

quicksort, 153-154, 159 ex., 160 pr., 162 pr.

randomized rounding, 1053

for searching a compact list, 218 pr.

for selection, 185-189

universal hashing, 232-236

worst-case performance of, 154 ex.

RANDOMIZED-HIRE-ASSISTANT, 100

RANDOMIZED-PARTITION, 154

RANDOMIZED-QUICKSORT, 154, 268 ex.

relation to randomly built binary search trees, 270 pr.

randomized rounding, 1053

RANDOMIZED-SELECT, 186

RANDOMIZE-IN-PLACE, 103

randomly built binary search tree, 265-268, 270 pr.

random-number generator, 94

random permutation, 101-104

uniform, 93, 101

random sampling, 154

RANDOM-SEARCH, 118 pr.

random variable, 1106-1111

indicator, see indicator random variable

range, 1078

rank

column, 731

full, 731

of a matrix, 731, 734 ex.

of a node in a disjoint-set forest, 506, 511-512, 518 ex.

of a number in an ordered set, 302

in order-statistic trees, 304-306, 307 ex.

row, 731

rate of growth, 26

ray, 940 ex.

RB-DELETE, 288

RB-DELETE-FIXUP, 289

RB-ENUMERATE, 311 ex.

RB-INSERT, 280

RB-INSERT-FIXUP, 281

RB-JOIN, 295 pr.

reachability in a graph (

), 1081

real numbers (R), 1070

reconstructing an optimal solution in dynamic programming, 346-347

record (data), 123

rectangle, 317 ex.

recurrence, 32, 62-90

solution by Akra-Bazzi method, 89-90

solution by master method, 73-76

solution by recursion-tree method, 67-72

solution by substitution method, 63-67

recurrence equation, see recurrence

recursion, 28

recursion tree, 36, 67-72

for merge sort, 349 ex.

in proof of master theorem, 76-78

and the substitution method, 70-72

RECURSIVE-ACTIVITY-SELECTOR, 376

RECURSIVE-FFT, 835

RECURSIVE-MATRIX-CHAIN, 345

red-black tree, 273-301

augmentation of, 309-310

compared to B-trees, 440

deletion from, 288-294

in determining whether any line segments intersect, 943

for enumerating keys in a range, 311 ex.

height of, 274

insertion into, 280-287

joining of, 295 pr.

maximum key of, 276

minimum key of, 276

predecessor in, 276

properties of, 273-277

relaxed, 276 ex.

restructuring, 428 pr.

rotation in, 277-279

searching in, 276

successor in, 276

and 2-3-4 trees, 441 ex.

reducibility, 984-986

reduction algorithm, 970, 984

reduction function, 984

reflexive relation, 1075

reflexivity of asymptotic notation, 49

region, feasible, 773

rejection

by an algorithm, 976

by a finite automaton, 917

RELABEL, 673

relabeled vertex, 673

relabel operation (in push-relabel algorithms), 672-673, 677

RELABEL-TO-FRONT, 687

relabel-to-front algorithm, 681-692

relation, 1075-1077

relatively prime, 854

RELAX, 586

relaxation

of an edge, 585-587

linear programming, 1041

relaxed heap, 497

relaxed red-black tree, 276 ex.

release time, 402 pr.

remainder, 51, 851

remainder instruction, 22

repeat, in pseudocode, 19

repeated squaring

for all-pairs shortest paths, 625-627

for raising a number to a power, 879

repetition factor of a string, 931 pr.

REPETITION-MATCHER, 931 pr.

representative of a set, 498

RESET, 412 ex.

residual capacity, 651, 654

residual edge, 652

residual network, 651-653

residue, 51, 851, 903 pr.

respect a set of edges, 563

return instruction, 22

reweighting

in all-pairs shortest paths, 636

in single-source shortest paths, 615 pr.

rho heuristic, 897-901, 901 ex.

ρ(n)-approximation algorithm, 1022

RIGHT, 128

right child, 1089

right-convert, 279 ex.

right horizontal ray, 940 ex.

RIGHT-ROTATE, 278

right rotation, 277

right spine, 296 pr.

right subtree, 1089

root

of a tree, 1087

of unity, 830-831

, 877

rooted tree, 1087

representation of, 214-217

root list

of a binomial heap, 459

of a Fibonacci heap, 478

rotation

cyclic, 930 ex.

in a red-black tree, 277-279

rotational sweep, 947, 949-955

rounding, 1042

randomized, 1053

row rank, 731

row vector, 726

RSA public-key cryptosystem, 881-887

rule of product, 1095

rule of sum, 1094

running time, 23

average-case, 26

best-case, 27 ex., 46

of a comparison network, 707

expected, 26

of a graph algorithm, 526

order of growth, 26

rate of growth, 26

worst-case, 26, 46