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