 | Greene D.H. Mathematics for the analysis of algorithms / D.H.Greene, D.E.Knuth. - 3rd ed., repr. of the 1990 ed. - Boston: Birkhäuser, 2008. - viii, 132 p.: ill. - (Modern Birkhauser classics). - Bibliogr.: p.77-80. - ISBN 978-0-8176-4728-5
|
1 Binomial Identities .......................................... 1
1.1 Summary of Useful Identities ............................ 1
1.2 Deriving the Identities ................................. 3
1.3 Inverse Relations ....................................... 5
1.4 Operator Calculus ....................................... 8
1.5 Hypergeometric Series ................................... 9
1.6 Identities with the Harmonic Numbers ................... 10
2 Recurrence Relations ........................................ 11
2.1 Linear Recurrence Relations ............................ 11
2.1.1 Finite History .................................. 12
2.1.1.1 Constant Coefficients .................. 12
2.1.1.2 Variable Coefficients .................. 14
2.1.2 Full History .................................... 17
2.1.2.1 Differencing ........................... 17
2.1.2.2 By Repertoire .......................... 17
2.2 Nonlinear Recurrence Relations ......................... 21
2.2.1 Relations with Maximum or Minimum Functions ..... 21
2.2.2 Continued Fractions and Hidden Linear
Recurrences ..................................... 25
2.2.3 Doubly Exponential Sequences .................... 27
3 Operator Methods ............................................ 31
3.1 The Cookie Monster ..................................... 31
3.2 Coalesced Hashing ...................................... 34
3.3 Open Addressing: Uniform Hashing ....................... 38
3.4 Open Addressing: Secondary Clustering .................. 39
4 Asymptotic Analysis ......................................... 42
4.1 Basic Concepts ......................................... 42
4.1.1 Notation ........................................ 43
4.1.2 Bootstrapping ................................... 43
4.1.3 Dissecting ...................................... 44
4.1.4 Limits of Limits ................................ 45
4.1.5 Summary of Useful Asymptotic Expansions ......... 47
4.1.6 An Example from Factorization Theory ............ 48
4.2 Stieltjes Integration and Asymptotics .................. 55
4.2.1 O-notation and Integrals ........................ 57
4.2.2 Euler's Summation Formula ....................... 58
4.2.3 An Example from Number Theory ................... 60
4.3 Asymptotics from Generating Functions .................. 65
4.3.1 Darboux's Method ................................ 65
4.3.2 Residue Calculus ................................ 68
4.3.3 The Saddle Point Method ......................... 70
Bibliography ................................................ 77
Appendices ..................................................... 81
A Schedule of Lectures, 1980 ............................... 81
B Homework Assignments ..................................... 83
C Midterm Exam I and Solutions ............................. 84
D Final Exam I and Solutions ............................... 95
E Midterm Exam II and Solutions ........................... 101
F Final Exam II and Solutions ............................. 107
G Midterm Exam III and Solutions .......................... 111
H Final Exam III and Solutions ............................ 116
I A Qualifying Exam Problem and Solution .................. 124
Index ......................................................... 129
|
|
