January Lectures

Week of January 3-4

Jan 3: No lecture this day (it will be taught later in the term).

Week of January 7-11

Jan 7: Introduction to the course. Administrative stuff. What is this course about.
Jan 10: Overview of the steps in the analysis of an algorithm. Analysis of Quicksort.

Week of January 14-18

Jan 14: Analysis of Quicksort (cont). Comments on variants.
Jan 17: Introduction to ordinary generating functions. Examples. Solving recurrences with generating functions.

Week of January 21-25

Jan 21: Solving recurrences with generating functions (cont). Analysis of Quicksort via generating functions.
Jan 24: Introduction to exponential generating functions. Examples. Comments on other generating functions. Real asymptotics. [A1 out]

Week of January 28 - February 1

Jan 28: Asymptotic expansions; Taylor expansions. Examples. Manipulation rules for asymptotic expansions.
Jan 31: Comments about assignment 1. Bootstrapping. Bounding tails of sums.

To February lectures.