Selected papers on the analysis of algorithms

✍ Scribed by Donald E. Knuth

• Publisher: Center for the Study of Language and Inf
• Year: 2000
• Tongue: English
• Leaves: 635
• Edition: 0
• Category: Library

✦ Synopsis

Donald Knuth's influence in computer science ranges from the invention of methods for translating and defining programming languages to the creation of the TeX and METAFONT systems for desktop publishing. His award-winning textbooks have become classics; his scientific papers are widely referenced and stand as milestones of development over a wide range of topics. The present volume, which is the fourth in a series of his collected works, is devoted to an important subfield of Computer Science that Knuth founded in the 1960s and still considers his main life's work. This field, to which he gave the name Analysis of Algorithms, deals with quantitative studies of computer techniques, leading to methods for understanding and predicting the efficiency of computer programs. More than 30 of the papers that helped to shape this field are reprinted and updated in the present collection, together with historical material that has not previously been published.

✦ Table of Contents

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