Behavior of Algorithms
MIT OpenCourseWare offers this graduate-level seminar on theoretical computer science, focused on rigorous methods for explaining why algorithms perform well in practice even when worst-case analysis suggests otherwise. The course centers on three analytical frameworks: smoothed analysis, which studies performance under small random perturbations of inputs; condition numbers and parametric analysis, which measure sensitivity to input structure; and subclassing inputs, which restricts attention to realistic input families rather than adversarial worst cases. Materials include lecture notes and readings drawn from current research papers in the field, reflecting the course's stated aim of tracking topics of ongoing interest that shift from term to term. The course is aimed at students already comfortable with algorithm design and analysis who want to go beyond standard worst-case and average-case frameworks. As with other MIT OCW offerings, materials are free to access and no certificate is issued.