CSCI2952-U

Beyond Worst Case Analysis of Algorithms

Offered this year and every year

Fall 2024

The theoretical study of algorithms and data structures has focused mostly on worst-case analysis, where we prove bounds on the running time, space, approximation ratio, competitive ratio, or other measure that holds even in the worst case. More and more, however, the limitations of worst-case analysis become apparent and create new challenges. In practice, we often do not face worst-case scenarios, and the question arises of how we can tune our algorithms to work even better on the kinds of instances we are likely to see, while ideally keeping a rigorous formal framework of analysis. In this graduate seminar course, we will review several alternatives to worst-case analysis, developed largely in the theoretical computer science literature over the past 20 years, and their most notable algorithmic applications. Subjects include: parametrized analysis, instance optimality, semirandom models, smoothed analysis, comparative analysis, and