290 INDEX
Key values, 42, 43, 73
Knapsack Problem, 222n2
Knuth, Donald, 71
Knuth-Morris-Pratt algorithm, 125, 272
analysis of, 127-128
Knuth-Morris-Pratt automaton,121
completed, 126
Kruskal’s algorithm, 159, 161
Kruskal’s minimum spanning tree
algorithm, 161
trace, 275-276
L
Las Vegas algorithms, 246-249, 250
Leclerc, Georges Louis, 241
Linear equations, 116-119
Gauss-Jordan method, 117-119
systems of, solved with SIMD algorithm,
205-206
Linear network
configuration, 181
sort, 191-195
Linear parallel network sort, 193 , 194 , 195
Linear time
Boolean variable problem solved in, 218
Lists
maximum values found in, 187-189
Logarithms, 14-15
Loops, 24, 38
Loosely coupled machines, 180-181
Lower bounds
for sorting algorithms, 28-31
M
Majority element, 245-246
Matching algorithms, 121-140
approximate string matching, 136-138
jump array, 132-134
programming exercises, 139-140
slide array, 130-132
string matching, 122-135
Mathematical background, 13-18
binary trees, 15
logarithms, 14-15
probabilities, 15-16
summations, 16-18
Mathematical calculations, 106
Matrices, 106
Matrix multiplication, 107, 112-116, 214, 215
algorithm, 5
in CRCW PRAM model, 204
dynamic, 255-257
on parallel mesh, 198-204
standard, 271
Strassen’s, 115-116
Winograd’s, 113-114
work needed to multiply four matrices in
different orders, 256
Matrix singularity, 205
Maximization problems, 220, 233
Maximum value
finding, in list, 187-189
MergeLists, 83, 84, 88, 97, 99
analysis, 85-86
Merge sort, 58, 83-88
analysis, 86-88
chapter study suggestion results for,
268-269
MergeLists analysis of, 85-86
MergeSort analysis of, 86-88
parallel version of, 197
Mesh network, 182 , 198, 199