Design and Analysis of Algorithms
This intermediate MIT algorithms course, taught by Erik Demaine, Srini Devadas, and Nancy Lynch, emphasizes techniques for designing and analyzing efficient algorithms rather than just implementing them. Topics include divide-and-conquer, randomization, dynamic programming, greedy algorithms, incremental improvement, complexity, and cryptography, delivered through lecture videos, lecture notes, recitation videos and notes, problem sets with solutions, and exams with solutions. It is cross-listed between Electrical Engineering and Computer Science and Mathematics, reflecting its proof-heavy approach compared to a more implementation-focused course like 6.006. Students typically take it after an introductory algorithms class, and it prepares you to analyze the correctness and running time of algorithms rigorously.