Selected Papers on the Analysis of Algorithms

Contents......Page 5
1 Mathematical Analysis of Algorithms......Page 15
2 The Dangers of Computer Science Theory......Page 33
3 The Analysis of Algorithms......Page 41
4 Big Omicron and Big Omega and Big Theta......Page 49
5 Optimal Measurement Points for Program Frequency Counts......Page 57
6 Estimating the Efficiency of Backtrack Programs......Page 69
7 Ordered Hash Tables......Page 91
8 Activity in an Interleaved Memory......Page 115
9 An Analysis of Alpha-Beta Pruning......Page 119
10 Notes on Generalized Dedekind Sums......Page 163
11 The Distribution of Continued Fraction Approximations......Page 195
12 Evaluation of Porter\'s Constant......Page 203
13 The Subtractive Algorithm for Greatest Common Divisors......Page 209
14 Length of Strings for a Merge Sort......Page 219
15 The Average Height of Planted Plane Trees......Page 229
16 The Toilet Paper Problem......Page 239
17 An Analysis of Optimum Caching......Page 249
18 A Trivial Algorithm Whose Analysis Isn\'t......Page 271
19 Deletions That Preserve Randomness......Page 297
20 Analysis of a Simple Factorization Algorithm......Page 317
21 The Expected Linearity of a Simple Equivalence Algorithm......Page 355
22 Textbook Examples of Recursion......Page 405
23 An Exact Analysis of Stable Allocation......Page 429
24 Stable Husbands......Page 443
25 Shellsort With Three Increments......Page 461
26 The Average Time for Carry Propagation......Page 481
27 Linear Probing and Graphs......Page 487
28 A Terminological Proposal......Page 499
29 Postscript About NP-Hard Problems......Page 507
30 An Experiment in Optimal Sorting......Page 509
31 Duality in Addition Chains......Page 515
32 Complexity Results for Bandwidth Minimization......Page 519
33 The Problem of Compatible Representatives......Page 549
34 The Complexity of Nonuniform Random Number Generation......Page 559
Index......Page 619