PRELIMINARIES
Why Do We Analyze Algorithms?
Proofs
Iteration and Recursion
COMBINATORICS
Properties of Summation
Multiple Sums
Principles of Counting
Permutations and Combinations
Binomial Coefficients
Binomial Coefficient and Hypergeometric Functions
Stirling Approximation
PROBABILITY
Set Operations
Sample Space and Random Variables
Calculating Probabilities
Random Variables
Conditional Probabilities
Independence
Joint Distributions
Dependent Random Variables
MORE ABOUT PROBABILITY
Special Distributions
Types of Probabilistic Convergence
The Theorem of Total Probability
Bayes’ Theorem
Convolution
Order Statistics
Chebyshev Inequality
Sundry Examples
RECURRENCES OR DIFFERENCE EQUATIONS
How Do Difference Equations Arise?
Properties of Difference Equations
First Order Linear Difference Equations
Divide-and-Conquer Recurrences
Quicksort Recurrence
Recurrences in Numerical Analysis
Continued Fractions
Partial Difference Equations
Some Applications
INTRODUCTION TO GENERATING FUNCTIONS
Generating Functions—Definitions
Extraction of Coefficients
Counting Binary Trees
Solving Recurrences
Snake Oil Summation
Applications in Probability
The Langrage Inversion Theorem
ENUMERATION WITH GENERATING FUNCTIONS
Definition of Enumerators
Sum and Product Rules
Counting Compositions of Integers
Further Set Operations
Partition of Integers
Exponential Enumerators
FURTHER ENUMERATION METHODS
Enumeration of Trees
Occupancy Enumeration
The Principle of Inclusion and Exclusion (PIE)
Extensions and Further Applications of the PIE
Probabilistic Inclusion-Exclusion Principle
Runs in Permutations
Special Topics
COMBINATORICS OF STRINGS
Operations on Languages
Regular Languages
Counting Regular Languages
Waiting Time Probabilistic Problems
Algorithms and Markov Chains
INTRODUCTION TO ASYMPTOTICS
Asymptotic Notation and Applications
The Critical Range Method
Rice’s Method
The Euler Summation Formula
Finding Primes
Asymptotics from Recurrences
Limit Laws in Probability
ASYMPTOTICS AND GENERATING FUNCTIONS
Elementary Bounds from Generating Functions
Estimates from Singularities
Estimates from Entire Functions
Examples and Exercises
REVIEW OF ANALYTIC TECHNIQUES
Complex Numbers
Review of Power Series
Functions of a Complex Variable: Basic Concepts
Differential Operators
Partial Fraction Decomposition
Some Special Functions
Stieltjes Integrals
APPENDICES
BIBLIOGRAPHY
ANSWERS/HINTS TO SELECTED PROBLEMS
INDEX
Biography
Vladimir A. Dobrushkin is a professor in the Division of Applied Mathematics at Brown University and a professor in the Department of Computer Science at Worcester Polytechnic Institute.
…helpful to any mathematics student who wishes to acquire a background in classical probability and analysis … This is a remarkably beautiful book that would be a pleasure for a student to read, or for a teacher to make into a year's course.
—Harvey Cohn, Computing Reviews, May 2010
