Beyond Worst-Case Analysis (Lecture 1: Three Motivating Examples)

Three motivating examples. Pros and cons of worst-case analysis. Instance optimality. Full course playlist: https://www.youtube.com/playlist?list=PLEGCF-WLh2RL8jsZpaf2tLHa5LotFEt5b Book: https://www.amazon.com/dp/1108494315 Lecture notes: http://timroughgarden.org/f14/l/l1.pdf