INDEX 295Set description
for digraph, 147
Sets, 144, 145
partitioning, 172-174
Shell, Donald L., 68
Shellsort, 58, 68-72
algorithm analysis, 70-71
chapter study suggestion results, 267
effect of increment on, 71-72
four passes of, 69
Sherwood algorithms, 249-250
Sherwood-based binary search, 250
shift, 7 4
Shortest-path algorithms, 163-167, 216, 224,
225, 233
Shortest-path parallel algorithm, 207-209
Shortest path tree
completed, starting at node A, 166
SIMD algorithm
systems of linear equations solved with,
205-206
SIMD machines. See Single instruction multi-
ple data machines
Sine, 106
Sine waves, 107
Single instruction multiple data machines, 179
Single instruction single data model, 179
Slide arrays, 129, 130-132
Slide value
deciding on, 131
Sliding
problem with, 129
Smarandache function, 226
Sorted list
key value in, 42
Sorting algorithms, 5, 11, 57-104, 214
bubble sort, 63-66
external polyphase merge sort, 95-100
heapsort, 77-82
insertion sort, 59-61
lower bounds for, 28-31
merge sort, 83-88
quicksort, 89-93
radix sort, 73-76
shellsort, 68-72
shortest-path and, 224, 225
Space complexity, 9-10
Space efficiency
and radix sort, 76
Spanning tree, 143
Speed up
of parallel algorithm, 182
Spell checkers, 122
Square
circle inscribed within, 241
Square matrices, 107
for Strassen’s algorithm, 115
Stack data structure, 151
start, 47, 48
Storage
of graphs, 143
Straightforward algorithm
tracing, 122
Strassen’s algorithm, 271
Strassen’s matrix multiplication, 106, 115-116
String matching, 122-135
approximate, 136-138
Boyer-Moore algorithm, 128-135
finite automata, 124-125
Knuth-Morris-Pratt algorithm, 125-128