Mathematics for the analysis of algorithms Daniel H. Greene, Donald E. Knuth

περιεχει βιβλιογραφια περιέχει προβλήματα

1. Binomial Identities 1.1 Summary of Useful Identities 1.2 Deriving the Identities 1.3 Inverse Relations 1.4 Operator Calculus 1.5 Hypergeometric Series 1.6 Identities with thw Harmonic Numbers 2. Recurrence Relations 2.1 Linear Recurrence Relations 2.1.1 Finite History 2.1.1.1 Constant Coefficients 2.1.1.2 Variable Coefficients 2.1.2 Full History 2.1.2.1 Differencing 2.1.2.2 By Repertoire 2.2 Nonlinear Recurrence Relations 2.2.1 Relations with Maximum or Minimum Functions 2.2.2 Continued Fractions and Hidden Linear Recurrences 2.2.3 Doubly Exponential Sequences 3. Operator Methods 3.1 The Cookie Monster 3.2 Coalesced Hashing 3.3 Open Addressing : Uniform Hashing 3.4 Open Addressing : Secondary Clustering 4. Asymptotic Analysis 4.1 Basic Concepts 4.1.1 Notation 4.1.2 Bootstrapping 4.1.3 Dissecting 4.1.4 Limits of Limits 4.1.5 Summary of Useful Asymptotic Expansions 4.1.6 An Example from Factorization Theory 4.2 Stieltjes Integration and Asymptotics 4.2.1 O - notation and Integrals 4.2.2 Euler's Summation Formula 4.2.3 An Example from Number Theory 4.3 Asymptotics from Generating Functions 4.3.1 Darboux's Method 4.3.2 Residue Calculus 4.3.3. The Saddle Point Method Bibliography Appendices A. Schedule of lectures, 1980 B. Homework Assignments C. Midterm Exam I and Solutions D. Final Exam II and Solutions E. Midterm Exam II and Solutions F. Final Exam II and Solutions G. Midterm Exam III and Solutions H. Final Exam III and Solutions I. A Qualifying Exam Problem and Solution Index