Lectures: 2 sessions / week, 1.5 hours / session
This is a graduate course on the design and analysis of algorithms, covering several advanced topics not studied in typical introductory courses on algorithms.
Prerequisites include "Introduction to algorithms" (at the level of 18.410J / 6.046J), linear algebra (at the level of 18.06 or 18.700), and mathematical maturity (since we'll be doing a lot of correctness proofs). The course is especially designed for doctoral students interested in theoretical computer science.
There will be biweekly problem sets and students will also be expected to take turns to scribe lecture notes. It is thanks to the scribes that we can have a good set of lecture notes with many details.
There is no textbook required for the course. Lecture notes are available for the current term as well as selected lecture notes from a previous term. Reference textbooks for each topic are listed in the readings section.
Topics we will be covering this year include: