ADVANCED ALGORITHMS

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.
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) 
29. 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.)
1. HW1    [PDF]
2. HW2    [PDF]
3. HW3    [PDF]