Mathematics for the Analysis of Algorithms

by Greene, Daniel H.; Knuth, Donald E.

• ISBN13: 9780817647285
• ISBN10: 0817647287
• Edition: 3rd
• Format: Paperback
• Copyright: 2007-10-05
• Publisher: Birkhauser

Summary

A quantitative study of the efficiency of computer methods requires an in-depth understanding of both mathematics and computer science. This monograph, derived from an advanced computer science course at Stanford University, builds on the fundamentals of combinatorial analysis and complex variable theory to present many of the major paradigms used in the precise analysis of algorithms, emphasizing the more difficult notions. The authors cover recurrence relations, operator methods, and asymptotic analysis in a format that is terse enough for easy reference yet detailed enough for those with little background. Approximately half the book is devoted to original problems and solutions from examinations given at Stanford.

Table of Contents

Binomial Identities	p. 1
Summary of Useful Identities	p. 1
Deriving the Identities	p. 3
Inverse Relations	p. 5
Operator Calculus	p. 8
Hypergeometric Series	p. 9
Identities with the Harmonic Numbers	p. 10
Recurrence Relations	p. 11
Linear Recurrence Relations	p. 11
Finite History	p. 12
Constant Coefficients	p. 12
Variable Coefficients	p. 14
Full History	p. 17
Differencing	p. 17
By Repertoire	p. 17
Nonlinear Recurrence Relations	p. 21
Relations with Maximum or Minimum Functions	p. 21
Continued Fractions and Hidden Linear Recurrences	p. 25
Doubly Exponential Sequences	p. 27
Operator Methods	p. 31
The Cookie Monster	p. 31
Coalesced Hashing	p. 34
Open Addressing: Uniform Hashing	p. 38
Open Addressing: Secondary Clustering	p. 39
Asymptotic Analysis	p. 42
Basic Concepts	p. 42
Notation	p. 43
Bootstrapping	p. 43
Dissecting	p. 44
Limits of Limits	p. 45
Summary of Useful Asymptotic Expansions	p. 47
An Example from Factorization Theory	p. 48
Stieltjes Integration and Asymptotics	p. 55
O-notation and Integrals	p. 57
Euler's Summation Formula	p. 58
An Example from Number Theory	p. 60
Asymptotics from Generating Functions	p. 65
Darboux's Method	p. 65
Residue Calculus	p. 68
The Saddle Point Method	p. 70
Bibliography	p. 77
Appendices	p. 81
Schedule of Lectures, 1980	p. 81
Homework Assignments	p. 83
Midterm Exam I and Solutions	p. 84
Final Exam I and Solutions	p. 95
Midterm Exam II and Solutions	p. 101
Final Exam II and Solutions	p. 107
Midterm Exam III and Solutions	p. 111
Final Exam III and Solutions	p. 116
A Qualifying Exam Problem and Solution	p. 124
Index	p. 129
Table of Contents provided by Ingram. All Rights Reserved.