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].