Beyond Worst-Case Analysis of Algorithms (CS 880)

I sat in on a topics course for CS 880, Beyond Worst-Case Analysis. In this course we explored what alternative methods to Big-Oh notation could be used to compare the efficiency of algorithms. At the time (2015) the creator of Big-Oh notation was still alive (I believe) and the theory of time complexity analysis was still being developed.

Here’s a nice course description from Shuchi Chawla (super nice person btw):

The theory of the design and analysis of algorithms has traditionally focused on providing provable guarantees in the worst case. In many situations such guarantees are overly pessimistic or inadequate. For example, many caching algorithms achieve the same optimal worst case performance ratio but their practical performance can vary greatly. Another example is that of the simplex algorithm for linear programming that has a worst case exponential time complexity, but is very efficient in practice. In these cases, worst-case analysis is not adequate in predicting the real performance of an algorithm, and not adequate in prescribing which algorithm to use in practice. In this course, we will study alternatives to worst-case analysis that avoid the above pitfalls but are at the same time rigorous and robust. Topics include but are not limited to stochastic models, planted or stable solution models, average-case analysis, parameterized analysis, and smoothed analysis.

We roughly followed the course from Tim Roughgarden’s Stanford CS course CS264: Beyond Worst-Case Analysis

We wrote our own rough draft lecture notes. I helped with lectures 2 and 3 on the Skyline problem, so I especially like that problem (haha). We tried to leave references where we could at the bottom of the notes.

  • Lecture 22 — incomplete and unedited
  • Lecture 21
  • Lecture 20
  • Lecture 19 — lightly edited
  • Lecture 16 — unedited
  • Lecture 15 — lightly edited
  • Lecture 14
  • Lecture 13 — lightly edited
  • Lecture 12 — lightly edited
  • Lecture 11
  • Lecture 10
  • Lecture 9 — unedited
  • Lecture 8
  • Lecture 7
  • Lecture 6
  • Lecture 5
  • Lecture 4
  • Lecture 3
  • Lecture 2
  • Lecture 1 — incomplete

Update: Aug 12/17 I decided to not link to these lectures since they are unedited in some cases and I didn’t ask for permission to post them. I have however left up two lectures which I personally helped write.