Course Description
Algorithm design and analysis is a fundamental and important part of computer science. This course introduces students to advanced techniques for the design and analysis of algorithms, and explores a variety of applications.
The topics and applications that we plan to cover include hashing, bloom filters, scheduling, network design, online load balancing, algorithms in machine learning, boosting (in the context of learning), Markov chains and the MCMC method, byzantine agreement, internet algorithms, and nearest neighbor algorithms. Enroute, we will encounter various useful ideas, including randomization, probabilistic analysis, amortized analysis, competitive analysis, eigenvalues, linear and semi-definite programming, high dimensional geometry, and random walks.
Download Lectures in PDF
1. 09/05 W [PDF] Intro, greedy algorithms: scheduling, MST. (K&T §4, §5) 2. 09/07 F [PDF] Set cover, Divide & Conquer, Dynamic programming. (K&T §5, §6, §11.3) 3. 09/10 M [PDF] Dynamic programming. (K&T §6) 4. 09/12 W [PDF] Network flow. (K&T §7) 5. 09/14 F [PDF] Network flow applications, matchings. (K&T §7) 6. 09/17 M [PDF] Randomized algorithms, Karger's min-cut algorithm. (K&T §13)
Here are some lecture notes by Avrim Blum on how to speed-up Karger's algorithm. 7. 09/19 W [PDF] Randomized load balancing and hashing. (K&T §13.10, §13.6, M&R §8.4, §8.5) 8. 09/21 F [PDF] Bloom filters, NP-completeness. (M&R §8.4, §8.5, M&U §5.5)
See also, this survey on the applications of bloom filters by Broder & Mitzenmacher. 9. 10/01 M [PDF] NP-completeness contd., Approximation algorithms. (K&T §8, Vaz. §1) 10. 10/03 W [PDF] Approximation via local search. 11. 10/08 M [PDF] Linear programming, LP rounding. (Vaz. §14) 12. 10/10 W [PDF] Randomized rounding, concentration bounds. (M&R §3.2, §4.1, §4.2) 13. 10/15 M [PDF] Randomized rounding (contd.), LP duality. (M&R §4.2, Vaz. §12) 14. 10/17 W [PDF] LP duality, Primal-dual algorithms. (Vaz. §12, 15) 15. 10/19 F [PDF] Primal-dual algorithms. (Vaz. §15) 16. 10/22 M [PDF] Semi-definite Programming. (Vaz. §26) 17. 10/24 W [PDF] SDP (contd.), Streaming algorithms. 18. 10/26 F [PDF] Streaming algorithms (contd.).
See this survey by Muthu Muthukrishnan for some motivation behind, and math used in, streaming algorithms. 19. 10/29 M [PDF] Online algorithms & competitive analysis. (B&E-Y §1)
Here is a nice presentation by Pat Riley & Elly Winner about different approaches to evaluating online algorithms. 20. 10/31 W [PDF] Caching/Paging, k-server problem. (B&E-Y §3, §4, §10) 21. 11/05 M [PDF] Caching lower bound based on Yao's principle, Work function algorithm. (B&E-Y §8.4, §10, §12)
For a complete analysis of the work function and other k-server algorithms, see these detailed lecture notes (lectures 5-9) by Yair Bartal. 22. 11/07 W [PDF] Work function (contd.), Online learning: regret minimization & the weighted majority algorithm. 23. 11/12 M [PDF] Mistake bound model, winnow & perceptron algorithms. 24. 11/14 W [PDF] MB model contd., PAC model. (K&V §1, §2) 25. 11/16 F [PDF] PAC model, Occam's razor. (K&V §1, §2) 26. 11/19 M [PDF] Boosting in the PAC framework. (K&V §4) 27. 11/26 M [PDF] Random Walks & Markov chains. Cover time, hitting time. (M&R §6) 28. 12/07 F [PDF] Random Walks & Markov chains: the resistance method, and mixing time. (M&R §6)
