Selected Papers on Analysis of Algorithms

by Donald E. Knuth

Overview

Analysis of Algorithms is the fourth in a series of collected works by world-renowned computer scientist Donald Knuth. This volume 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 book 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.

Product Details

ISBN-13:	9781575862125
Publisher:	Center for the Study of Language and Inf
Publication date:	07/05/2001
Series:	Lecture Notes , #102
Edition description:	New Edition
Pages:	540
Product dimensions:	6.00(w) x 9.00(h) x 1.30(d)

About the Author

Donald E. Knuth is professor emeritus of the art of computer science at Stanford University. He is the author of 3:16 Bible Texts Illuminated and the multivolume work in progress The Art of Computer Programming.

Table of Contents

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

Editorial Reviews

The fourth volume of influential computer scientist Knuth's collected papers is devoted to a specialty he founded in the 1960s to deal with quantitative studies of computer techniques and predict the efficiency of computer programs. He has added updated material to most of the 34 papers. Distributed in the US by Cambridge U. Press. Annotation c. Book News, Inc., Portland, OR (booknews.com)

Booknews