Analysis of Algorithms : An Active Learning Approach

INDEX 289

Graph algorithms, 141-175
biconnected component algorithm,
168-171
breadth-first traversals, 151-153
depth-first traversals, 150-151
Dijkstra-Prim algorithm, 155-158
graph background/terminology, 144-146
Kruskal algorithm, 159-161
miminum spanning tree algorithm,
155-161
partitioning sets, 172-174
shortest-path algorithm, 163-167
traversal analysis, 153
Graph coloring, 228-229, 238-239
Graphs, 142, 145
data structure methods for, 147-149
storing, 143
types of, 143
Greatest common divisor, 31
Greedy algorithm, 155, 232-239
Growth rates, 2, 20-23

H
Hamilton circuit, 219
Hamilton path, 219
Heap
construction, 77, 79
list implementation for, 78
Heapsort, 58, 77-82
average-case analysis for, 82
chapter study suggestion results, 267-268
final algorithm, 80
fixheap, 78-79
heap construction, 79
worst-case analysis, 80-82
Horner’s method, 108, 270

Hypercube, 182

I

Image analysis, 107

includedCount variable, 161

Increment

effect of, in shellsort, 71-72

increment variable, 69, 70

Indexes

and biconnected component algorithm,

170

Initialization, 6

Input classes, 7-8

Insertion sort, 59-62, 89

average-case analysis of, 60-62

chapter study suggestion results for,

265-266

shellsort’s reliance on, 71

worst-case analysis of, 60

InsertionSort function, 70

Intractable problems, 215

Inversions

in shellsort, 70

J

Java, 7

Job scheduling, 223, 227-228

Johnson, D., 220

Jump array, 129, 132-134

calculation for “datadata” analysis, 134

Jump value determination, 132

K

Keys, 42, 43, 95

changing comparison of, 58

in radix sort, 74