ISBN: 0-201-40009-X
- Chapter One: Analysis of Algorithms
- Why Analyze an Algorithm?
- Computational Complexity
- Analysis of Algorithms
- Average-Case Analysis
- Example: Analysis of Quicksort
- Asymptotic Approximations
- Distributions
- Probabilistic Algorithms
- Chapter Two: Recurrence Relations
- Basic Properties
- First-Order Recurrences
- Nonlinear First-Order Recurrences
- Higher-Order Recurrences
- Methods for Solving Recurrences
- Binary Divide-and-Conquer Recurrences and Binary Numbers
- General Divide-and-Conquer Recurrences
- Chapter Three: Generating Functions
- Ordinary Generating Functions
- Exponential Generating Functions
- Generating Function Solution of Recurrences
- Expanding Generating Functions
- Transformations with Generating Functions
- Functional Equations on Generating Functions
- Solving the Quicksort Median-of-Three
- Recurrence with OGFs
- Counting with Generating Functions
- The Symbolic Method
- Lagrange Inversion
- Probability Generating Functions
- Bivariate Generating Functions
- Special Functions
- Chapter Four: Asymptotic Approximations
- Notation for Asymptotic Approximations
- Asymptotic Expansions
- Manipulating Asymptotic Expansions
- Asymptotic Approximations of Finite Sums
- Euler-Maclaurin Summation
- Bivariate Asymptotics
- Laplace Method
- "Normal'' Examples from the Analysis of Algorithms
- "Poisson'' Examples from the Analysis of Algorithms
- Generating Function Asymptotics
- Chapter Five: Trees
- Binary Trees
- Trees and Forests
- Properties of Trees
- Tree Algorithms
- Binary Search Trees
- Average Path Length in Catalan Trees
- Path Length in Binary Search Trees
- Additive Parameters of Random Trees
- Height
- Summary of Average-Case Results on Properties of Trees
- Representations of Trees and Binary Trees
- Unordered Trees
- Labelled Trees
- Other Types of Trees
- Chapter Six: Permutations
- Basic Properties of Permutations
- Algorithms on Permutations
- Representations of Permutations
- Enumeration Problems
- Analyzing Properties of Permutations with CGFs
- Inversions and Insertion Sorts
- Left-to-Right Minima and Selection Sort
- Cycles and In Situ Permutation
- Extremal Parameters
- Chapter Seven: Strings and Tries
- String Searching
- Combinatorial Properties of Bitstrings
- Regular Expressions
- Finite-State Automata and Knuth-Morris-Pratt Algorithm
- Context-Free Grammars
- Tries
- Trie Algorithms
- Combinatorial Properties of Tries
- Larger alphabets
- CHAPTER EIGHT: WORDS AND MAPS
- Hashing with Separate Chaining
- Basic Properties of Words
- Birthday Paradox and Coupon Collector Problem
- Occupancy Restrictions and Extremal Parameters
- Occupancy Distributions
- Open Addressing Hashing
- Maps
- Integer Factorization and Maps