R

| < Day Day Up > |

# 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.
see also interval tree, order-statistic tree
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
of , 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

| < Day Day Up > |