# 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.

LECTURE | CHAPTER | TOPIC | READING |
---|---|---|---|

1 | One | Analysis of algorithms | 3-39 |

2 | Two | Recurrences | 41-89 |

3 | Three | Generating functions | 91-149 |

4 | Four | Asymptotics | 151-217 |

5 | Five | Analytic combinatorics | 219-255 |

6 | Six | Trees | 257-344 |

7 | Seven | Permutations | 345-413 |

8 | Eight | Strings and Tries | 415-471 |

9 | Nine | 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.