6.1220: Design and Analysis of Algorithms
We learned about:
- Probability (review), divide and conquer, randomized algorithms, amortized analysis, competitive analysis, hashing, and MST algorithms (Part 1).
- Maximum flow and minimum cuts, linear programming and duality properties, and intractability through NP-Complete reductions (Part 2).
- Approximation algorithms, multiplicative weights, random walks and Markov chains, the fast fourier transform, sublinear time algorithms, and streaming algorithms (Part 3).
As part of this, we practiced writing algorithmic proofs with a decent level of rigor.