# Lecture Slides

These slides are for the first half of an undergraduate course taught at Princeton, developed to provide an overview of An Introduction to the Analysis of Algorithms and Analytic Combinatorics.

The course format is "introduce-read-discuss". We introduce a set of topics in lecture; students read about the topics and work selected exercises between lectures, and we discuss any questions about the reading and the exercises at the beginning of the next lecture. Each lecture ends with a slide or two giving assignments to be completed before the next lecture and to be discussed at the beginning of the next lecture. In addition, a portion of each lecture is devoted to in-class exercises, to make sure that all students understand the introductory material.

While some of the reading material may be difficult for a typical undergraduate to master on such a quick pass through, a substantial fraction of the coverage is elementary. One purpose of the discussion format is to help students learn to master the elementary material so as to be able to understand the key concepts.

Lecture slides are available both in 1-up format (accessible by clicking the lecture name when it is activated as a link) and in “4-up” format (accesible by editing the extension -2x2 to the filename in your browser). Example: Lecture 1 slides are in the file AA01-AofA.pdf, accessible by clicking “Analysis of Algorithms” in the “Topic” column. The 4-up version is in the file AA01-AofA-2x2.pdf. Chapter and page numbers refer to the second edition of the book.

1One Analysis of algorithms 3-39
2Two Recurrences 41-89
3Three Generating functions 91-149
4Four Asymptotics 151-217
5Five Analytic combinatorics 219-255
6Six Trees 257-344
7Seven Permutations 345-413
8Eight Strings and Tries 415-471
9Nine Words and Mappings 473-541

## Errata in Lecture slides

• Lecture 1, slide 33. Should be $${a (10 N) \ln (10 N)\over a N\ln N} = 10\Bigl(1 + {\ln 10\over\ln N}\Bigr) = 10\Bigl( 1 + {1\over\log_{10}N}\Bigr)$$ and therefore 4 x 12 = 48 seconds for N = 1M and 48 x (70/6) x (80/7) x (90/8) = 20 hours for N = 1B.

• Lecture 2, slide 15. Should be $2(H_{n+1}-1)$ just to the left of the telescope.

• Lecture 2, slide 29. Need $a_0$ in telescoped result, so solution should be $B_N = \lg N + 1$.

• Lecture 2, slides 31, 32, 33, 35, and 38. Initial condition for Mergesort recurrence should be $C_1 = 0$.

• Lecture 2, slide 42. < and > should be switched in the Master Theorem.

• Lecture 3, slide 20. Polynomial should be $z^t-x_1z^{t-1}-+x_2z^{t-2}-\ldots-x_tz^{0}.$

• Lecture 3, slide 34. Missing summation sign before the binomial coefficient on line 3 (sum on $k$ from 0 to $n$).

• Lecture 4, slide 6. decreasing series -> decreasing sequence.

• Lecture 4, slide 36. negligible -> negligable.

• Lecture 8, slides 8 and 18. $\beta_k$ is the dominant root of $1-2z+z^k$ -> $1/\beta_k$ is the smallest root of $1-2z+z^k$ .

• Lecture 13, slide 4. Not correct to say that o-notation is for lower bounds.