Externally indexed torrent

If you are the original uploader, contact staff to have it moved to your account

Textbook in PDF format

This monograph is derived from an advanced course in computer science at Stanford University on the analysis of algorithms. The course presents
examples of the major paradigms used in the precise analysis of algorithms, emphasizing some of the more difficult techniques. Much of the material is drawn from the starred sections of The Art of Computer Programming, Volume 3 [Knuth III]. Analysis of algorithms, as a discipline, relies heavily on both computer science and mathematics. This report is a mathematical look at the synthesis--emphasizing the mathematical perspective, but using motivation and examples from computer science. It covers binomial identities, recurrence relations, operator methods and asymptotic analysis, hopefully in a format that is terse enough for easy reference and yet detailed enough to be of use to those who have not attended the lectures. However, it is assumed that the reader is familiar with the fundamentals of complex variable theory and combinatorial analysis.
Winter 1980 was the fourth offering of Analysis of Algorithms, and credit is due to the previous teachers and staff--Leo Guibas, Scott Drysdale, Sam
Bent, Andy Yao, and Phyllis Winkler--for their detailed contributions to the documentation of the course. Portions of earlier handouts are incorporated in this monograph. Harry Mairson, Andrei Broder, Ken Clarkson, and Jeff Vitter contributed helpful comments and corrections, and the
preparation of these notes was also aided by the facilities of Xerox corporation and the support of NSF and Hertz graduate fellowships.
In this third edition we have made a few improvements to the exposition and fixed a variety of minor errors. We have also added several new
appendices containing exam problems from 1982 and 1988.
Binomial Identities
Summary of Useful Identities
Deriving the Identities
Inverse Relations
Operator Calculus
Hypergeometric Series
Identitieswith the Harmonic Numbers
Recurrence Relations
Linear Recurrence Relations
Finite History
Constant Coefficients
Variable Coefficients
Full History
Differencing
By Repertoir e
Nonlinear Recurrence Relations
Relations with Maximum or Minimum Functions
Continued Fractions and Hidden Linear Recurrences
Doubly Exponential Sequences
Operator Methods
The Cookie Monster
Coalesced Hashing
Open Addressing: Uniform Hashing
Open Addressing: Secondary Clustering
Asymptotic Analysis
Basic Concepts
Notation
Bootstrapping
Dissecting
Limits of Limits
Summary of Useful Asymptotic Expansions
An Example from Factorization Theory
Stieltjes Integration and Asymptotics
O-notation and Integrals
Euler's Summation Formula
An Example from Number Theory
Asymptotics from Generating Functions
Darboux's Method
Residue Calculus
The Saddle Point Method
Bibliography
Appendices
A Schedule of Lectures,
B Homework Assignments
C Midterm Exam I and Solutions
D Final Exam I 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