Mathematics for the Analysis of Algorithms

Front Cover
Springer Science & Business Media, Sep 1, 1990 - Computers - 132 pages

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.

 

 

What people are saying - Write a review

We haven't found any reviews in the usual places.

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
Index
129
Copyright

Other editions - View all

Common terms and phrases

About the author (1990)

Gary Greene's colored pencil paintings and articles have appeared in various books and magazines, including"International Artist", "American Artist" and "The Encyclopedia of Colored Pencil Techniques". Gary's paintings have won national and international awards, and his work has been purchased and showcased by corporations around the world. He has conducted workshops, demonstrations and lectures nationally and internationally since 1985. He is a fifteen-year signature member of the Colored Pencil Society of America and served on its founding Board of Directors for six years.

Donald E. Knuth is known throughout the world for his pioneering work on algorithms and programming techniques, for his invention of the Tex and Metafont systems for computer typesetting, and for his prolific and influential writing. Professor Emeritus of The Art of Computer Programming at Stanford University, he currently devotes full time to the completion of these fascicles and the seven volumes to which they belong.

Bibliographic information