Analysis of Algorithms : An Active Learning Approach

REFERENCES 283 Metropolis, I. and Ulam, S. “The Monte Carlo Method,” Journal of the American Statistical Association, 44(247), p ...

This page intentionally left blank ...

Index Note: Italicized page locators indicate figures. A Ackermann’s function, 226 Addition in polynomial calculations, 110, 111 ...

286 INDEX Average-case analysis(continued) of Quicksort, 91-93 for sequential search, 44-45 B Backpack approximation, 236 Backpa ...

INDEX 287 Comparisons, 95 in bubble sort, 65, 66 inMergeLists, 85, 86 in run construction, 99 in run merge, 99-100 in shellsort, ...

288 INDEX Dynamic programming, 138, 252-257 array-based methods, 252-255 dynamic matrix multiplication, 255-257 E edgeCount vari ...

INDEX 289 Graph algorithms, 141-175 biconnected component algorithm, 168-171 breadth-first traversals, 151-153 depth-first trave ...

290 INDEX Key values, 42, 43, 73 Knapsack Problem, 222n2 Knuth, Donald, 71 Knuth-Morris-Pratt algorithm, 125, 272 analysis of, 1 ...

INDEX 291 Message transmission and shortest-path table, 167 middle, 47, 48 MIMD system. See Multiple instruction multi- ple data ...

292 INDEX Numerical probabilistic algorithms(continued) Buffon’s needle, 241-242 Monte Carlo integration, 242-243 probabilistic ...

INDEX 293 Pivot element and quicksort, 89 PivotList function, 90, 91, 92 relationship between indices and element values in, 90 ...

294 INDEX Quicksort (continued) splitting the list, 90-91 worst-case analysis of, 91 R Radix sort, 58, 73-76 analysis, 74-76 cha ...

INDEX 295 Set description for digraph, 147 Sets, 144, 145 partitioning, 172-174 Shell, Donald L., 68 Shellsort, 58, 68-72 algori ...

296 INDEX Study suggestion results, 265-278 Boyer-Moore, 273 breadth-first traversal, 273 bubble sort, 266 depth-first traversal ...

INDEX 297 Traveling salesperson approximations, 233-234 problem, 215-217 Traversal algorithms breadth-first, 151-153 depth-first ...