INDEX 291Message transmission
and shortest-path table, 167
middle, 47, 48
MIMD system. See Multiple instruction multi-
ple data system
Minimization problems, 220, 232, 233
Minimum spanning tree, 142, 143
algorithms, 172, 233
completed, rooted at node A, 158
and Dijkstra-Prim algorithm, 155-158
and Kruskal algorithm, 159-161
parallel algorithm, 209-211
and shortest-path algorithm, 163
MISD machine. See Multiple instruction single
data machine
Mixed congruential method, 261
Modulus, 11
Monic polynomials, 109
Monte Carlo algorithms, 244-246, 250
majority element, 245-246
Monte Carlo prime testing, 246
Monte Carlo integration, 242-243
MST. See Minimum spanning tree
Multiple instruction multiple data system,
180
Multiple instruction single data machine,
179-180
Multiplication
in polynomial calculations, 110, 111
of 2 x 3 matrix and 3 x 4 matrix, 112
Multiplicative operators (multiplications), 11
Multitasking systems, 178
N
Nodes, 153
and biconnected component algorithm,
168, 169, 170
and breadth-first traversals, 151, 152, 153
and depth-first traversals, 150, 151
and graph coloring, 220, 221
of graphs, 142, 144, 145
and shortest-path algorithm, 207, 208
and shortest path tree, 165, 166
Nondeterministic algorithms, 213-229
factors determining class NP, 224-226
NP-complete problems, 218-220
NP defined/discussed, 214-217
problem reductions, 217-218
testing possible solutions, 226-229
typical NP problems, 220-223
Nondeterministic polynomial time complexity
for problems of class NP, 215
Nonrecursive algorithms, 151
NP class, 232
defined/discussed, 214-217
optimal solution for problems in, 232-233
NP-complete problems, 218-220
NP problems, 220-223, 224-225
backpack problem, 222
bin packing, 221-222
CNF-satisfiability problem, 222-223
graph coloring, 220-221
is P = NP?, 225-226
job scheduling problem, 223
subset sum problem, 222
Numeric algorithms, 105-119
linear equations, 116-119
matrix multiplication, 112-116
polynomial calculations, 107-111
Numerical probabilistic algorithms, 232,
240-244, 250