Design and Analysis of Algorithms

6.046J is MIT's intermediate algorithms course, and the spring 2015 edition taught by Erik Demaine, Srini Devadas and Nancy Lynch is fully recorded on OpenCourseWare. It assumes you can already analyse simple algorithms and data structures at the level of 6.006, and concentrates on techniques for designing efficient algorithms and analysing sophisticated ones. Listed topics are divide-and-conquer, randomisation, dynamic programming, greedy algorithms, incremental improvement, complexity and cryptography. The twenty-three lectures move from interval scheduling and divide-and-conquer examples such as convex hull, median finding, the FFT and van Emde Boas trees, through amortised analysis, randomised algorithms including skip lists and universal hashing, range trees, advanced dynamic programming, minimum spanning trees, max-flow and matching, linear programming, P versus NP and reductions, approximation and fixed-parameter algorithms, synchronous and asynchronous distributed algorithms, hash functions and encryption, and cache-oblivious algorithms.

Recitation videos and notes accompany the lectures, and the site includes lecture notes, problem sets with solutions, and exams with solutions, plus instructor insights. The course objectives state that students should be able to write rigorous correctness proofs and synthesise efficient algorithms for engineering situations. Everything is free under a Creative Commons licence; no account or certificate.