292 INDEX
Numerical probabilistic algorithms(continued)
Buffon’s needle, 241-242
Monte Carlo integration, 242-243
probabilistic counting, 243-244
O
Object transformations
4 x 4 matrices for, 107
Odd-even parallel sort, 197
Odd-even swap sort, 195-196
Operations
and algorithms, 2
classes of, 10
Optimization problems, 220
Order, 22
P
Parallel algorithms, 177-212
parallel graph, 207-211
parallel numerical, 198-206
parallel searching, 189-191
parallel sorting, 191-197
PRAM model, 183-185
simple parallel operations, 185-189
Parallel architectures, 180-182
looselyversus tightly coupled machines,
180-181
processor communication, 181-182
Parallel blocks, 206, 211
Parallel graph algorithms, 207-211
minimum spanning tree parallel algo-
rithm, 209-211
shortest-path parallel algorithm, 207-209
Parallelism
analysis principles, 182-183
computer system categories, 179-180
introduction to, 178-183
Parallel merge techniques, 197
Parallel mesh
matrix multiplication on, 198, 200-203
Parallel numerical algorithms, 198-206
matrix multiplication in CRCW PRAM
model, 204
matrix multiplication on parallel mesh,
198-204
systems of linear equations solved with
SIMD algorithm, 205-206
Parallel operations
simple, 185-189
Parallel random access machine, 184
model, 183-185
Parallel searching, 189-191
Parallel sorting, 191-197
algorithm, 183
linear network sort, 191-195
odd-even swap sort, 195-196
other types of, 196-197
Parent array, 172, 173
Partitioning sets, 172-174
Pascal, 7
Pascal’s Triangle, 254
patternLoc, 130, 131
P class, 215
as subset of class NP, 224
PDAs. See Personal digital assistants
Penalties
and job scheduling, 228
Personal digital assistants, 9
“Phone tree,” 143
Pipelined systems, 178