Mathematics for the Analysis of AlgorithmsA quantitative study of the efficiency of computer methods requires an indepth 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.

What people are saying  Write a review
Contents
Binomial Identities  1 
12 Deriving the Identities  3 
13 Inverse Relations  5 
14 Operator Calculus  8 
15 Hypergeometric Series  9 
16 Identities with the Harmonic Numbers  10 
Recurrence Relations  11 
211 Finite History  12 
415 Summary of Useful Asymptotic Expansions  47 
416 An Example from Factorization Theory  48 
42 Stieltjes Integration and Asymptotics  55 
421 Onotation and Integrals  57 
422 Eulers Summation Formula  58 
423 An Example from Number Theory  60 
43 Asymptotic from Generating Functions  65 
432 Residue Calculus  68 
2112 Variable Coefficients  14 
212 Full History  17 
22 Nonlinear Recurrence Relations  21 
222 Continued Fractions and Hidden Linear Recurrences  25 
223 Doubly Exponential Sequences  27 
Operator Methods  31 
32 Coalesced Hashing  34 
Uniform Hashing  38 
Secondary Clustering  39 
4 Asymptotic Analysis  42 
411 Notation  43 
413 Dissecting  44 
414 Limits of Limits  45 
433 The Saddle Point Method  70 
Bibliography  77 
Schedule of Lectures 1980  81 
Homework Assignments  83 
Midterm Exam I and Solutions  84 
Final Exam I and Solutions  95 
Midterm Exam II and Solutions  101 
Final Exam II and Solutions  107 
Midterm Exam III and Solutions  111 
Final Exam III and Solutions  116 
A Qualifying Exam Problem and Solution  124 
129  
Other editions  View all
Mathematics for the Analysis of Algorithms Daniel H. Greene,Donald E. Knuth No preview available  2007 