Chapter 1: Analysis of Algorithms 31.1 Why Analyze an Algorithm? 31.2 Theory of Algorithms 61.3 Analysis of Algorithms 131.4 Average-Case Analysis 161.5 Example: Analysis of Quicksort 181.6 Asymptotic Approximations 271.7 Distributions 301.8 Randomized Algorithms 33 Chapter 2: Recurrence Relations 412.1 Basic Properties 432.2 First-Order Recurrences 482.3 Nonlinear First-Order Recurrences 522.4 Higher-Order Recurrences 552.5 Methods for Solving Recurrences 612.6 Binary Divide-and-Conquer Recurrences and Binary Numbers 702.7 General Divide-and-Conquer Recurrences 80 Chapter 3: Generating Functions 913.1 Ordinary Generating Functions 923.2 Exponential Generating Functions 973.3 Generating Function Solution of Recurrences 1013.4 Expanding Generating Functions 1113.5 Transformations with Generating Functions 1143.6 Functional Equations on Generating Functions 1173.7 Solving the Quicksort Median-of-Three Recurrence with OGFs 1203.8 Counting with Generating Functions 1233.9 Probability Generating Functions 1293.10 Bivariate Generating Functions 1323.11 Special Functions 140 Chapter 4: Asymptotic Approximations 1514.1 Notation for Asymptotic Approximations 1534.2 Asymptotic Expansions 1604.3 Manipulating Asymptotic Expansions 1694.4 Asymptotic Approximations of Finite Sums 1764.5 Euler-Maclaurin Summation 1794.6 Bivariate Asymptotics 1874.7 Laplace Method 2034.8 "Normal" Examples from the Analysis of Algorithms 2074.9 "Poisson" Examples from the Analysis of Algorithms 211 Chapter 5: Analytic Combinatorics 2195.1 Formal Basis 2205.2 Symbolic Method for Unlabelled Classes 2215.3 Symbolic Method for Labelled Classes 2295.4 Symbolic Method for Parameters 2415.5 Generating Function Coefficient Asymptotics 247 Chapter 6: Trees 2576.1 Binary Trees 2586.2 Forests and Trees 2616.3 Combinatorial Equivalences to Trees and Binary Trees 2646.4 Properties of Trees 2726.5 Examples of Tree Algorithms 2776.6 Binary Search Trees 2816.7 Average Path Length in Catalan Trees 2876.8 Path Length in Binary Search Trees 2936.9 Additive Parameters of Random Trees 2976.10 Height 3026.11 Summary of Average-Case Results on Properties of Trees 3106.12 Lagrange Inversion 3126.13 Rooted Unordered Trees 3156.14 Labelled Trees 3276.15 Other Types of Trees 331 Chapter 7: Permutations 3457.1 Basic Properties of Permutations 3477.2 Algorithms on Permutations 3557.3 Representations of Permutations 3587.4 Enumeration Problems 3667.5 Analyzing Properties of Permutations with CGFs 3727.6 Inversions and Insertion Sorts 3847.7 Left-to-Right Minima and Selection Sort 3937.8 Cycles and In Situ Permutation 4017.9 Extremal Parameters 406 Chapter 8: Strings and Tries 4158.1 String Searching 4168.2 Combinatorial Properties of Bitstrings 4208.3 Regular Expressions 4328.4 Finite-State Automata and the Knuth-Morris-Pratt Algorithm 4378.5 Context-Free Grammars 4418.6 Tries 4488.7 Trie Algorithms 4538.8 Combinatorial Properties of Tries 4598.9 Larger Alphabets 465 Chapter 9: Words and Mappings 4739.1 Hashing with Separate Chaining 4749.2 The Balls-and-Urns Model and Properties of Words 4769.3 Birthday Paradox and Coupon Collector Problem 4859.4 Occupancy Restrictions and Extremal Parameters 4959.5 Occupancy Distributions 5019.6 Open Addressing Hashing 5099.7 Mappings 5199.8 Integer Factorization and Mappings 532 List of Theorems 543List of Tables 545List of Figures 547Index 551