Ebook: An introduction to the analysis of algorithms

Machine generated contents note: ch. One Analysis of Algorithms --

1.1. Why Analyze an Algorithm? --

1.2. Theory of Algorithms --

1.3. Analysis of Algorithms --

1.4. Average-Case Analysis --

1.5. Example: Analysis of Quicksort --

1.6. Asymptotic Approximations --

1.7. Distributions --

1.8. Randomized Algorithms --

ch. Two Recurrence Relations --

2.1. Basic Properties --

2.2. First-Order Recurrences --

2.3. Nonlinear First-Order Recurrences --

2.4. Higher-Order Recurrences --

2.5. Methods for Solving Recurrences --

2.6. Binary Divide-and-Conquer Recurrences and Binary Numbers --

2.7. General Divide-and-Conquer Recurrences --

ch. Three Generating Functions --

3.1. Ordinary Generating Functions --

3.2. Exponential Generating Functions --

3.3. Generating Function Solution of Recurrences --

3.4. Expanding Generating Functions --

3.5. Transformations with Generating Functions --

3.6. Functional Equations on Generating Functions --

3.7. Solving the Quicksort Median-of-Three Recurrence with OGFs --

3.8. Counting with Generating Functions --

3.9. Probability Generating Functions --

3.10. Bivariate Generating Functions --

3.11. Special Functions --

ch. Four Asymptotic Approximations --

4.1. Notation for Asymptotic Approximations --

4.2. Asymptotic Expansions --

4.3. Manipulating Asymptotic Expansions --

4.4. Asymptotic Approximations of Finite Sums --

4.5. Euler-Maclaurin Summation --

4.6. Bivariate Asymptotics --

4.7. Laplace Method --

4.8."Normal" Examples from the Analysis of Algorithms --

4.9."Poisson" Examples from the Analysis of Algorithms --

ch. Five Analytic Combinatorics --

5.1. Formal Basis --

5.2. Symbolic Method for Unlabelled Classes --

5.3. Symbolic Method for Labelled Classes --

5.4. Symbolic Method for Parameters --

5.5. Generating Function Coefficient Asymptotics --

ch. Six Trees --

6.1. Binary Trees --

6.2. Forests and Trees --

6.3.Combinatorial Equivalences to Trees and Binary Trees --

6.4. Properties of Trees --

6.5. Examples of Tree Algorithms --

6.6. Binary Search Trees --

6.7. Average Path Length in Catalan Trees --

6.8. Path Length in Binary Search Trees --

6.9. Additive Parameters of Random Trees --

6.10. Height --

6.11. Summary of Average-Case Results on Properties of Trees --

6.12. Lagrange Inversion --

6.13. Rooted Unordered Trees --

6.14. Labelled Trees --

6.15. Other Types of Trees --

ch. Seven Permutations --

7.1. Basic Properties of Permutations --

7.2. Algorithms on Permutations --

7.3. Representations of Permutations --

7.4. Enumeration Problems --

7.5. Analyzing Properties of Permutations with CGFs --

7.6. Inversions and Insertion Sorts --

7.7. Left-to-Right Minima and Selection Sort --

7.8. Cycles and In Situ Permutation --

7.9. Extremal Parameters --

ch. Eight Strings and Tries --

8.1. String Searching --

8.2.Combinatorial Properties of Bitstrings --

8.3. Regular Expressions --

8.4. Finite-State Automata and the Knuth-Morris-Pratt Algorithm --

8.5. Context-Free Grammars --

8.6. Tries --

8.7. Trie Algorithms --

8.8.Combinatorial Properties of Tries --

8.9. Larger Alphabets --

ch. Nine Words and Mappings --

9.1. Hashing with Separate Chaining --

9.2. The Balls-and-Urns Model and Properties of Words --

9.3. Birthday Paradox and Coupon Collector Problem --

9.4. Occupancy Restrictions and Extremal Parameters --

9.5. Occupancy Distributions --

9.6. Open Addressing Hashing --

9.7. Mappings --

9.8. Integer Factorization and Mappings.