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. Download all lectures notes in a single PDF file here.- 09/05 W [PDF] Intro, greedy algorithms: scheduling, MST. (K&T §4, §5)
- 09/07 F [PDF] Set cover, Divide & Conquer, Dynamic programming. (K&T §5, §6, §11.3)
- 09/10 M [PDF] Dynamic programming. (K&T §6)
- 09/12 W [PDF] Network flow. (K&T §7)
- 09/14 F [PDF] Network flow applications, matchings. (K&T §7)
- 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. - 09/19 W [PDF] Randomized load balancing and hashing. (K&T §13.10, §13.6, M&R §8.4, §8.5)
- 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. - 10/01 M [PDF] NP-completeness contd., Approximation algorithms. (K&T §8, Vaz. §1)
- 10/03 W [PDF] Approximation via local search.
- 10/08 M [PDF] Linear programming, LP rounding. (Vaz. §14)
- 10/10 W [PDF] Randomized rounding, concentration bounds. (M&R §3.2, §4.1, §4.2)
- 10/15 M [PDF] Randomized rounding (contd.), LP duality. (M&R §4.2, Vaz. §12)
- 10/17 W [PDF] LP duality, Primal-dual algorithms. (Vaz. §12, 15)
- 10/19 F [PDF] Primal-dual algorithms. (Vaz. §15)
- 10/22 M [PDF] Semi-definite Programming. (Vaz. §26)
- 10/24 W [PDF] SDP (contd.), Streaming algorithms.
- 10/26 F [PDF] Streaming algorithms (contd.).
See this survey by Muthu Muthukrishnan for some motivation behind, and math used in, streaming algorithms. - 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. - 10/31 W [PDF] Caching/Paging, k-server problem. (B&E-Y §3, §4, §10)
- 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. - 11/07 W [PDF] Work function (contd.), Online learning: regret minimization & the weighted majority algorithm.
- 11/12 M [PDF] Mistake bound model, winnow & perceptron algorithms.
- 11/14 W [PDF] MB model contd., PAC model. (K&V §1, §2)
- 11/16 F [PDF] PAC model, Occam's razor. (K&V §1, §2)
- 11/19 M [PDF] Boosting in the PAC framework. (K&V §4)
- 11/26 M [PDF] Random Walks & Markov chains. Cover time, hitting time. (M&R §6)
- 12/07 F [PDF] Random Walks & Markov chains: the resistance method, and mixing time. (M&R §6)
- 12/10 M Markov chains wrap-up and Q-A session.
No lecture notes are available for this last lecture, however, these notes contain all of what we covered, and extra.
Homeworks (Note: Solutions are no longer available here. Please email Shuchi for a copy.)- HW1 [PDF]
- HW2 [PDF]
- HW3 [PDF]
Thank you for reading the article about ADVANCED ALGORITHMS. If you want to duplicate this article you are expected to include links https://immunologyebooks.blogspot.com/2011/08/advanced-algorithms.html. Thank you for your attention.
