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.