S

| < Day Day Up > |

# Index

### S

safe edge, 562
SAME-COMPONENT, 500
sample space, 1100
sampling, 154
SAT, 996
satellite data, 123, 197
satisfiability, 988, 996– 998, 1039– 1040, 1043 ex.
satisfiable formula, 967, 996
satisfying assignment, 988, 996
saturated edge, 672
saturating push, 672, 678
scalar flow product, 650 ex.
scalar multiple, 729
scaling
in maximum flow, 694 pr.
in single-source shortest paths, 615 pr.
scapegoat tree, 301
schedule, 399, 1051 pr.
event-point, 942
scheduling, 369 pr., 402 pr., 1020 pr., 1051 pr.
Schur complement, 748, 761
Schur complement lemma, 761
SCRAMBLE-SEARCH, 118 pr.
SEARCH, 198
searching
binary search, 37 ex.
in binary search trees, 256– 258
in B-trees, 441– 442
in chained hash tables, 226
in compact lists, 218 pr.
in direct-address tables, 222
for an exact interval, 317 ex.
in interval trees, 314– 316
linear search, 21 ex.
in linked lists, 205
in open-address hash tables, 238
problem of, 21 ex.
in red-black trees, 276
an unsorted array, 118 pr.
search tree, see balanced search tree, binary
search tree, B-tree, exponential search
tree, interval tree, optimal binary search
tree, order-statistic tree, red-black tree,
splay tree, 2-3 tree, 2-3-4 tree
secondary clustering, 240
secondary hash table, 245
secondary storage
search tree for, 434– 454
stacks on, 452 pr.
second-best minimum spanning tree, 575 pr.
secret key, 881, 884
segment, see directed segment, line segment
SEGMENTS-INTERSECT, 937
SELECT, 189– 190
selection
of activities, see activity-selection problem
and comparison sorts, 192
in expected linear time, 185– 189
in order-statistic trees, 303– 304
problem of, 183
in worst-case linear time, 189– 193
selection sort, 27 ex.
selector vertex, 1009
self-loop, 1080
semiconnected graph, 557 ex.
sentinel, 29, 206– 208, 274
sequence (〈 〉)
bitonic, 618 pr., 712
clean, 713
finite, 1078
infinite, 1078
input, 705
inversion in, 39 pr., 99 ex.
output, 705
probe, 237
series, 86 pr., 1059– 1061
set ({}), 1070– 1075
convex, 650 ex.
independent, 1018 pr.
set-covering problem, 1033– 1038
weighted, 1050 pr.
set-partition problem, 1017 ex.
shadow of a point, 956 ex.
Shell's sort, 40
shift in string matching, 906
shift instruction, 22
short-circuiting operator, 20
SHORTEST-PATH, 968
shortest paths, 580– 642
all-pairs, 581, 620– 642
Bellman-Ford algorithm for, 588– 592
with bitonic paths, 618 pr.
and breadth-first search, 534– 537, 581
convergence property of, 587, 609
and difference constraints, 601– 607
Dijkstra's algorithm for, 595– 601
in a directed acyclic graph, 592– 595
in ∈-dense graphs, 641 pr.
estimate of, 585
Floyd-Warshall algorithm for, 629– 632
Gabow's scaling algorithm for, 615 pr.
Johnson's algorithm for, 636– 640
as a linear program, 785– 786
and longest paths, 966
by matrix multiplication, 622– 629
and negative-weight cycles, 582
with negative-weight edges, 582– 583
no-path property of, 587, 608– 609
optimal substructure of, 581– 582
path-relaxation property of, 587, 609– 610
predecessor-subgraph property of, 587, 612– 613
problem variants, 581
and relaxation, 585– 587
by repeated squaring, 625– 627
single-destination, 581
single-pair, 341, 581
single-source, 580– 619
tree of, 584, 610– 613
triangle inequality of, 587, 607– 608
in an unweighted graph, 341, 535
upper-bound property of, 587, 608
in a weighted graph, 580
sibling, 1088
side of a polygon, 939 ex.
signature, 883
simple cycle, 1081
simple graph, 1082
simple path, 1081
longest, 342, 966
simple polygon, 939 ex.
simple uniform hashing, 226
simplex, 775
SIMPLEX, 797
simplex algorithm, 775, 790– 804, 820– 821
single-destination shortest paths, 581
single-pair shortest path, 341, 581
as a linear program, 785– 786
single-source shortest paths, 580– 619
Bellman-Ford algorithm for, 588– 592
with bitonic paths, 618 pr.
and difference constraints, 601– 607
Dijkstra's algorithm for, 595– 601
in a directed acyclic graph, 592– 595
in ∈-dense graphs, 641 pr.
Gabow's scaling algorithm for, 615 pr.
and longest paths, 966
singleton, 1073
singly connected graph, 549 ex.
singly linked list, 204
see also linked list
singular matrix, 730
singular value decomposition, 769
sink, 530 ex., 644, 647
size
of an algorithm's input, 23, 849– 850, 973– 975
of a binomial tree, 457
of a boolean combinational circuit, 989
of a clique, 1003
of a comparison network, 707
of a set, 1073
of a sorting network, 708 ex.
of a subtree in a Fibonacci heap, 495
of a vertex cover, 1006, 1024
skew symmetry, 644
skip list, 301
slack, 781
slack form, 773, 781– 783
uniqueness of, 801
slack variable, 781
slot, 222
SLOW-ALL-PAIRS-SHORTEST-PATHS, 625
solution
to an abstract problem, 972
basic, 792
to a computational problem, 6
to a concrete problem, 973
feasible, 601, 773, 778
infeasible, 778
optimal, 778
to a system of linear equations, 742
sorted linked list, 204
see also linked list
SORTER, 719, 720 ex.
sorting, 15– 19, 28– 36, 123– 182
average-case lower bound for, 178 pr.
bubblesort, 38 pr.
bucket sort, 174– 177
comparison sort, 165
counting sort, 168– 170
fuzzy, 163 pr.
heapsort, 127– 144
insertion sort, 11, 15– 19
lexicographic, 269 pr.
in linear time, 168– 177, 178 pr.
lower bounds for, 165– 168
of a matrix, 721 ex.
merge sort, 11, 28– 36
network for, see sorting network
in place, 16, 124
of points by polar angle, 939 ex.
problem of, 5, 15, 123
quicksort, 145– 164
radix sort, 170– 173
selection sort, 27 ex.
Shell's sort, 40
topological, see topological sort
using a binary search tree, 264 ex.
using networks, see sorting network
variable-length items, 179 pr.
sorting network, 707
AKS, 724
based on insertion sort, 708 ex.
based on merge sort, 719– 721
bitonic, 712– 716
depth of, 708 ex., 720 ex.
odd-even, 721 pr.
size of, 708 ex.
source, 531, 581, 644, 647
spanning tree, 394, 561
bottleneck, 577 pr.
verification of, 579
see also minimum spanning tree
sparse graph, 527
sparse-hulled distribution, 964 pr.
spindle, 435
spine, 296 pr.
splay tree, 301, 432
spline, 767 pr.
splitting
of B-tree nodes, 443– 445
of 2-3-4 trees, 453 pr.
splitting summations, 1065– 1066
spurious hit, 912
square matrix, 726
square of a directed graph, 530 ex.
square root, modulo a prime, 903 pr.
squaring, repeated
for all-pairs shortest paths, 625– 627
for raising a number to a power, 879
stability
numerical, 725, 743, 769
of sorting algorithms, 170, 173 ex.
stack, 200– 201
in Graham's scan, 949
implemented by queues, 204 ex.
linked-list implementation of, 208 ex.
operations analyzed by accounting method, 410– 411
operations analyzed by aggregate analysis, 406– 408
operations analyzed by potential method, 413– 414
for procedure execution, 162 pr.
on secondary storage, 452 pr.
STACK-EMPTY, 201
standard deviation, 1110
standard form, 773, 777– 781
star-shaped polygon, 956 ex.
start state, 916
start time, 371
state of a finite automaton, 916
static graph, 499 n.
static set of keys, 245
Stirling's approximation, 55
STOOGE-SORT, 161 pr.
storage management, 127, 210– 212, 213 ex., 229 ex.
store instruction, 22
straddle, 936
Strassen's algorithm, 735– 742
streaks, 110– 114
strictly decreasing, 51
strictly increasing, 51
string, 906, 1095
string matching, 906– 932
based on repetition factors, 931 pr.
by finite automata, 916– 923
with gap characters, 910 ex., 923 ex.
Knuth-Morris-Pratt algorithm for, 923– 931
naive algorithm for, 909– 911
Rabin-Karp algorithm for, 911– 916
string-matching automaton, 917– 922, 923 ex.
strongly connected component, 1082
decomposition into, 552– 557
STRONGLY-CONNECTED-COMPONENTS, 554
strongly connected graph, 1082
subgraph, 1082
predecessor, see predecessor subgraph
subgraph-isomorphism problem, 1017 ex.
subgroup, 866– 868
subpath, 1081
subroutine
calling, 20, 22, 23 n.
executing, 23 n.
subsequence, 350
subset
hereditary family of, 393
independent family of, 393
subset (⊆), 1071
SUBSET-SUM, 1013
subset-sum problem
approximation algorithm for, 1043– 1049
NP-completeness of, 1013– 1017
with unary target, 1017 ex.
substitution method, 63– 67
and recursion trees, 70– 72
substring, 1095
subtract instruction, 22
subtraction of matrices, 729
subtree, 1087
maintaining sizes of, in order-statistic trees, 306– 307
success in a Bernoulli trial, 1112
successor
in binary search trees, 258– 259
finding ith, of a node in an order-statistic tree, 307 ex.
in linked lists, 204
in order-statistic trees, 310 ex.
in red-black trees, 276
SUCCESSOR, 198
suffix (⊏), 907
suffix function, 917
suffix-function inequality, 920
suffix-function recursion lemma, 920
sum
Cartesian, 830 ex.
flow, 650 ex.
infinite, 1058
of matrices, 728
of polynomials, 822
rule of, 1094
telescoping, 1061
summation, 1058– 1069
in asymptotic notation, 47, 1059
bounding, 1062– 1069
formulas and properties of, 1058– 1062
implicit, 648
linearity of, 1059
summation lemma, 832
superpolynomial time, 966
supersink, 647
supersource, 647
surjection, 1078
SVD, 769
sweeping, 940– 947, 962 pr.
sweep line, 940
sweep-line status, 942– 943
symbol table, 221, 230, 232
symmetric difference, 696 pr.
symmetric matrix, 728, 733– 734 ex.
symmetric positive-definite matrix, 760– 762
symmetric relation, 1075
symmetry of Θ-notation, 49
systems of difference constraints, 601– 607
systems of linear equations, 742– 755, 767 pr.

| < Day Day Up > |