296 INDEX
Study suggestion results, 265-278
Boyer-Moore, 273
breadth-first traversal, 273
bubble sort, 266
depth-first traversal, 273
Dijkstra-Prim spanning tree trace,
273-275
Dijkstra’s shortest-path algorithm,
276-278
Gauss-Jordan method, 272
heapsort, 267-268
Horner’s method, 270
insertion sort, 265-266
Knuth-Morris-Pratt, 272
Kruskal’s minimum spanning tree trace,
275-276
merge sort, 268-269
quicksort, 269
radix sort, 270
shellsort, 267
standard matrix multiplication, 271
Strassen’s algorithm, 271
Winograd’s matrix multiplication, 271
Subgraphs, 145, 155
subLoc, 128
Subprograms, 38
Subroutines, 38
Subset sum algorithm
results of first three passes of, 238
Subset sum approximation, 236-238
Subset sum problem, 222
Substitutions, 33-36, 117
Substrings, 122, 136
matches, 123
Subtrees, 49
Summation equations
simplifying, 18
Summations, 16-18
for quicksort, 92
swappedElements flag, 64
Swaps/swapping, 76, 95
in bubble sort, 63
in quicksort, 92
in shellsort, 71
Symbols
big oh, 22
big omega, 22
big theta, 23T
Target, 43
and average-case analysis for binary search,
51
for binary search, 46, 48
in worst-case analysis for sequential
search, 44
Testing
solutions of class NP, 226-229
textLoc, 128, 130, 131, 133
then clause
and set partitioning, 173
Tightly coupled machine, 181
Tournament method, 27-28, 187
Tournament tree
for set of eight values, 28
trace array, 256, 257
Trace/tracing
Dijkstra-Prim minimum spanning tree,
273-275
Kruskal’s minimum spanning tree,
275-276
parallel algorithms, 177
Tractable problems, 215