Analysis of Algorithms : An Active Learning Approach

INDEX 287

Comparisons, 95
in bubble sort, 65, 66
inMergeLists, 85, 86
in run construction, 99
in run merge, 99-100
in shellsort, 71
Computer-aided design and manufacturing,
106-107
Computer graphics, 106
Concurrent access, 184
Concurrent Read Concurrent Write, 185
Concurrent Read Exclusive Write, 185
Conjunctive normal form, 222
Connected graph, 146
with two biconnected components, 168
Contention times, 184
Convolution operations
matrices in, 107
Cook, S., 219
Cosine, 106
Cost
of parallel algorithm, 183
Counters
global, 38-39
CRCW. See Concurrent Read Concurrent
Write
CRCW PRAM model
matrix multiplication in, 204
CreateRuns, 9 8
CREW. See Concurrent Read Exclusive Write
CREW PRAM model
broadcasting data in, 186
minimum spanning tree algorithm for,
210
SIMD algorithm for, 205

Cycle, 146

D

Dataflow systems, 178

Data structure methods for graphs, 147-149

adjacency list, 149

adjacency matrix, 148

Decision problems, 220, 227

Decision trees, 29-31

for search of list of seven elements, 49

for sorting three-element list, 29

Decreasing first fit technique, 235, 236

Depth-first search tree, 169, 170

Depth-first traversals, 150-151, 273

Deterministic algorithms, 240

in polynomial time, 217

and Sherwood algorithms, 249

diffs matrix, 137

for substring “trim” and text “try the

trumpet,” 138

Digraphs, 147

Dijkstra, Edsger, 155

Dijkstra-Prim algorithm, 155-158

Dijkstra-Prim minimum spanning tree algo-

rithm, 142

Dijkstra-Prim minimum spanning tree trace,

273-275

Dijkstra’s algorithm, 164-167, 233

Dijkstra’s shortest-path algorithm, 276-278

Directed graphs (digraphs), 143, 144, 145

Divide and conquer algorithms, 2, 24-31, 26

DivideInput routine, 25

Division, 11

Dot product, 113

Dynamic matrix multiplication, 255-257