Analysis of Algorithms : An Active Learning Approach

INDEX 297

Traveling salesperson
approximations, 233-234
problem, 215-217
Traversal algorithms
breadth-first, 151-153
depth-first, 150-151
Traversal analysis, 153
Tree network, 182
Tree node
fringe node connected with, 156
Trigonometric functions, 106
Turing machine, 6, 7
Two-step nondeterministic process, 224
Typing errors, 136

U
Undirected graphs, 144, 220
Union function, 173
Unrooted tree, 146
Unsorted list, 42
Upper bound
worst case contrasted with, 44

V
Virtual memory, 96
Virtual memory swapping, 59
Virus checking, 122

W

Wave patterns, 107

Weighted connected graph

minimum spanning tree of, 155

Weighted graphs, 143, 146, 148

adjacency list entries for, 149

and adjacency matrix, 207

adjacency matrix for fully connected,

234

while loop

for insertion sort, 60

and Knuth-Morris-Pratt analysis, 127-128

Winograd’s algorithm

analysis of, 114

Winograd’s matrix multiplication, 106,

113-114, 271

Worst-case analysis, 12

of binary search, 48-49

of bubble sort, 64-65

of heapsort, 80-82

of insertion sort, 60

of quicksort, 91

of sequential search, 44

Y

Y2K bug problems, 9