Beyond Worst-Case Analysis
Course information
- Quarter: Spring 2025
- Lecture time: Tuesdays and Thursdays 1:30-2:50pm
- Lecture location: 260-113
- Prerequisites: Introductory algorithms class (e.g., CS 161). CS261 is recommended but not required.
Description
This course is motivated by algorithm design problems where traditional worst-case analysis fails to meaningfully distinguish between different solutions, or recommends an intuitively “wrong” solution over the “right” one. We systematically explore alternative frameworks to traditional worst-case analysis that provide rigorous and robust performance guarantees while overcoming these limitations. Topics include: instance optimality; smoothed analysis; parameterized analysis and condition numbers; models of data (pseudorandomness, locality, diffuse adversaries, etc.); average-case analysis; robust distributional analysis; resource augmentation; planted and semi-random graph models. Motivating problems will be drawn from online algorithms, online learning, constraint satisfaction problems, graph partitioning, scheduling, linear programming, hashing, machine learning, and auction theory.
Course structure
This course will be facilitated through in-person class meetings with the professor. All assignments will be posted on Canvas. Announcements will also be made through Canvas, and any questions should be posted to Ed.
- Lecture: Our class will meet on Tuesdays and Thursdays from 1:30-2:50 PM in 260-113.
- Homework: Students will submit four homework assignments on Gradescope (linked to on Canvas). The deadline for each homework will be Thursdays at 11:59pm.
- Project: Students will complete a course project, in a group or individually.
Grading
Grading will be out of 100 points as follows:
- Homeworks: 60 points (15 for each of four homeworks)
- Project: 40 points
Course materials
- Required textbook: Roughgarden (2021). Beyond the Worst-Case Analysis of Algorithms.
Stanford students can access it for free here.
Previous versions of this course
This course was originally developed by Tim Roughgarden [link].