CS787 - Advanced Algorithms Course (original) (raw)

Announcements

• 01/02. Solutions for homeworks and the final are no longer available on this page. Please feel free to email Shuchi if you would like a copy.
• 12/18. Final exam solutions are available here. (wisc.edu access only.)
• 12/10. The final exam is available now. It is due by midnight on Monday, Dec 17.
• 12/10. Lecture notes are now available in a single PDF filehere.
• 12/08. Solutions to HW3 are up now.
• 11/19. The take-home final exam will be out on Dec 10th (Monday) and due by midnight Dec 17th (Monday). You can email your final to me or slip it under my office door.
• 11/14. HW3 is up now. Note that you get slightlylonger than 3 weeks for this homework -- it is due on Dec 7th.
• 11/08. Solutions to HW2 are up now. See below.
• 11/06. Chi Man will not be holding office hours today. Instead, Shuchi is holding office hours from 3 to 4 pm today, and Chi Man will hold additional office hours on Friday from 1 to 2 pm.
• 10/31. Lecture 21 on Nov 5 will be a little longer than usual. We will end at 4 p.m. instead of 3:45 p.m.
• 10/17. HW2 and the solutions to HW1 are up now. See below.
• 10/09. There is no lecture on Oct 12. Instead you are encouraged to attend this talk by Kunal Talwar from Microsoft Research.
• 10/02. A clarification for question 5 on homework 1 is posted here.
• 09/19. There will be no lectures during the week of 9/24-28.
• 09/06. I sent out an announcement on the class mailing list this morning. If you did not receive this announcement but would like to be on the mailing list, please send me email.
• 08/09. Welcome! Please check this space frequently for announcements. More information about the syllabus, instructor, course work, etc. can be found here. 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. Read more ...

Scribe notes & readings Disclaimer: Drafts are likely to be incomplete and contain errors, so please check back for a final version.
The books referenced below are Borodin & El-Yaniv (B&E-Y), Kleinberg & Tardos (K&T), Kearns & Vazirani (K&V),
Motwani & Raghavan (M&R), Mitzenmacher & Upfal (M&U), and Vazirani (Vaz.). All are available at the Wendt library.

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

30. HW1 [PDF]

31. HW2 [PDF]

32. HW3 [PDF] Misc material

A template for scribe notes can be found

here.
Before scribing lectures, please read thisnote on mathematical writing by Knuth, Larrabee and Roberts.
Scribing assignments are available here.