Methods in Algorithmic Analysis Book

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