Selected Papers on Analysis of Algorithms

Donald E. Knuth is one of the world's pre-eminent computer scientists, whose works have had a profound influence on the subject since the publication in 1968 of the first volume of The Art of Computer Programming. Knuth created TeX, a language for typesetting mathematical and scientific texts, and METAFONT, a computer software system for alphabet design. He is professor emeritus at Stanford University.

1. An almost linear recurrence; 2. The problem of compatible representatives; 3. The analysis of algorithms; 4. Mathematical analysis of algorithms; 5. The average height of planted plane trees; 6. An experiment in optimal sorting; 7. Shellsort with three increments; 8. The dangers of computer science theory; 9. Optimum measurement points for program frequency counts; 10. Ordered Hash tables; 11. Recurrence relations based on minimization; 12. Estimating the efficiency of backtrack programs; 13. An analysis of alpha-beta pruning; 14. Linear probing and graphs; 15. Activity in an interleaved memory; 16. Notes on generalized Dedekind sums; 17. Analysis of the subtractive algorithm for greatest common divisors; 18. Complexity results for bandwidth minimization; 19. Analysis of a simple factorization algorithm; 20. The complexity of nonuniform random number generation; 21. A trivial algorithm whose analysis isn't; 22. Evaluation of Porter's constant; 23. The expectant linearity of a simple equivalence algorithm; 24. Deletions that preserve randomness; 25. The average time for carry propogation; 26. A terminological proposal; 27. An analysis of optimum caching; 28. Optimal prepaging and font caching; 29. The distribution of continued fraction approximations; 30. The toilet paper problem; 31. A recurrence related to trees; 32. Stable husbands; 33. Postscript about NP-hard problems; 34. Nested satisfiability; 35. Textbook examples of recursion; 36. An exact analysis of stable allocation; 37. Big omicron and big omega and big theta.