September Lectures

Week of September 4-5

Sep 4: Short lecture this day (complete lecture will be taught later in the term).

Week of September 8-12

Sep 9: Introduction to the course. Administrative stuff. What is this course about.
Sep 11: Overview of the steps in the analysis of an algorithm. Analysis of Quicksort.

Week of September 15-19

Sep 16: Comments on variants of Quicksort. Introduction to ordinary generating functions.
Sep 18: Ordinary generating functions (cont). Examples. Solving recurrences with generating functions.

Week of September 22-26

Sep 23: Analysis of Quicksort via generating functions. Introduction to exponential generating functions.
Sep 25: Introduction to exponential generating functions (cont). Examples. Comments on other generating functions. Real asymptotics. [A1 out]

Week of September 29 - October 2

Sep 30: Asymptotic expansions; Taylor expansions. Examples. Manipulation rules for asymptotic expansions.
Oct 2: Comments about assignment 1. Bootstrapping. Bounding tails of sums. Euler-MacLaurin formula.

To October lectures.