CS264: Beyond Worst-Case Analysis

Instructor: Tim Roughgarden (Office hours: Tuesdays 2-3 PM, Gates 474.)

Teaching Assistants:

Time/location: 10:30-11:50 AM on Tuesdays and Thursdays in Hewlett 102.

Piazza site: here

Course description: In the worst-case analysis of algorithms, the overall performance of an algorithm is summarized by its worst performance on any input. This approach has countless success stories, but there are also important computational problems --- like linear programming, clustering, and online caching --- where the worst-case analysis framework does not provide any helpful advice on how to solve the problem. This course covers a number of modeling methods for going beyond worst-case analysis and articulating which inputs are the most relevant.

List of topics: instance optimality; perturbation and approximate stability; smoothed analysis; parameterized analysis and condition numbers; models of data (pseudorandomness, locality, diffuse adversaries, etc.); robust analogs of average-case analysis; resource augmentation; planted and semi-random graph models; sparse recovery (like compressive sensing).

Motivating problems drawn from online algorithms, machine learning (topic models, clustering), computational geometry, graph partitioning, scheduling, linear programming, local search heuristics, social networks, hashing, signal processing, and empirical algorithmics.

Prerequisites: undergraduate algorithms (CS161, or equivalent). Prior exposure to linear programming is recommended but not required (review materials will be posted as needed).

Course requirements: Weekly exercise sets. Students have the option to substitute a paper-reading project for 3 of the exercise sets. No late assignments accepted, although we will drop the lowest of your 10 scores.

Previous offering (in 2014): here. Includes lecture videos and lecture notes. Note: the overlap between this and the previous offering will be roughly 50%.

Primer: for a two-hour overview of the entire course, see

Lecture notes

Additional background material:


Related workshops: Since this course debuted in 2009, there have been several workshops on the topic:

Detailed schedule and references (under construction):