CSLI Publications logo
new books
knuth books
for authors
CSLI Publications
Selected Papers on Analysis of Algorithms cover

Selected Papers on Analysis of Algorithms

2nd Printing

Donald E. Knuth

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 that are often credited for shaping the field; 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. Analysis of Algorithms, which has grown to be a thriving international discipline, is the unifying theme underlying Knuth's well known books The Art of Computer Programming. More than 30 of the fundamental 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. Although many ideas come and go in the rapidly changing world of computer science, the basic concepts and techniques of algorithmic analysis will remain important as long as computers are used.



  • 1. Mathematical Analysis of Algorithms 1
  • 2. The Dangers of Computer Science Theory 19
  • 3. The Analysis of Algorithms 27
  • 4. Big Omicron and Big Omega and Big Theta 35
  • 5. Optimal Measurement Points for Program Frequency Counts 43
  • 6. Estimating the Efficiency of Backtrack Programs 55
  • 7. Ordered Hash Tables 77
  • 8. Activity in an Interleaved Memory 101
  • 9. An Analysis of Alpha-Beta Pruning 105
  • 10. Notes on Generalized Dedekind Sums 149
  • 11. The Distribution of Continued Fraction Approximations 181
  • 12. Evaluation of Porter's Constant 189
  • 13. The Subtractive Algorithm for Greatest Common Divisors 195
  • 14. Length of Strings for a Merge Sort 205
  • 15. The Average Height of Planted Plane Trees 215
  • 16. The Toilet Paper Problem 225
  • 17. An Analysis of Optimum Caching 235
  • 18. A Trivial Algorithm Whose Analysis Isn't 257
  • 19. Deletions That Preserve Randomness 283
  • 20. Analysis of a Simple Factorization Algorithm 303
  • 21. The Expected Linearity of a Simple Equivalence Algorithm 341
  • 22. Textbook Examples of Recursion 391
  • 23. An Exact Analysis of Stable Allocation 415
  • 24. Stable Husbands 429
  • 25. Shellsort With Three Increments 447
  • 26. The Average Time for Carry Propagation 467
  • 27. Linear Probing and Graphs 473
  • 28. A Terminological Proposal 485
  • 29. Postscript About NP-hard Problems 493
  • 30. An Experiment in Optimal Sorting 495
  • 31. Duality in Addition Chains 501
  • 32. Complexity Results for Bandwidth Minimization 505
  • 33. The Problem of Compatible Representatives 535
  • 34. The Complexity of Nonuniform Random Number Generation 545
  • Index 605

ISBN (Paperback): 1575862123 (9781575862125)

Subject: Computer Science; Algorithms

Prof. Knuth's page on this book including table of contents and errata

Add to Cart
View Cart

Check Out

Distributed by the
University of
Chicago Press

pubs @ csli.stanford.edu