Instructor: Tim Roughgarden (Office hours: by appointment in Gates 462)
Teaching Assistant: Qiqi Yan (Office hours: Wednesdays and Thursday 3-4 PM in Gates 460; email: contact "at" qiqiyan.com)
Time/location: 10 AM-12:30 PM on Fridays in Hewlett 101.
Course description: Theoretical work in the design and analysis of algorithms commonly measures the performance of an algorithm (its running time and/or solution quality) using worst-case analysis. For many problems, the worst-case analysis framework successfully identifies non-trivial and useful algorithms (as seen in any undergraduate algorithms textbook). This course is motivated by problems for which traditional worst-case analysis is *not* useful, either because it fails to differentiate meaningfully between different solutions, or because it recommends an intuitively "wrong" solution over the "right" one. The plan is to study systematically alternatives to traditional worst-case analysis that nevertheless enable rigorous and robust guarantees on the performance of an algorithm.
Tentative list of topics: instance optimality; smoothed analysis; models of data (pseudorandomness, locality, diffuse adversaries, etc.); robust distributional analysis; resource augmentation; planted or semi-random graph models. Motivating problems will be drawn from online algorithms, online learning, graph partitioning, scheduling, linear programming, hashing, and auction theory.
Prerequisites: 154N and 161, or equivalents. 261 will be very helpful but is not strictly required.
Course requirements: 2-3 difficult problem sets, typically to be solved in groups.
Lecture notes: The good news is that I've finished first drafts of all of the lectures (around 100 pages total). The bad news is that I don't have many cycles available to finish editing, add references, etc. I'm posting the lectures here as I finish them, and hope to be done with them all some time in October 2010.
Syllabus and references.