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.
Reference books
There is no textbook required for the course. Lecture notes will be made available from the course web page. Please visit the course webpage frequently for extra reading material. Reference books for each topic are listed below. Some of these books (as specified below) have been placed on reserve in the Wendt library.
Approximation Algorithms
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.
Reference books
There is no textbook required for the course. Lecture notes will be made available from the course web page. Please visit the course webpage frequently for extra reading material. Reference books for each topic are listed below. Some of these books (as specified below) have been placed on reserve in the Wendt library.
Approximation Algorithms
- Vijay Vazirani, Approximation Algorithms, Springer, 2001. (on reserve)
- Dorit S. Hochbaum (ed.), Approximation Algorithms for NP-hard Problems, PWS Publishing, 1997. (on reserve)
- Rajeev Motwani and Prabhakar Raghavan, Randomized Algorithms, Cambridge University Press, 2000. (on reserve)
- Michael Mitzenmacher and Eli Upfal, Probability and Computing, Cambridge University Press, 2005.
- Allan Borodin and Ran El-Yaniv, Online Computation and Competitive Analysis, Cambridge University Press, 2005. (on reserve)
- Michael Kearns and Umesh Vazirani, An Introduction to Computational Learning Theory, The MIT Press, 1994. (on reserve)
- Jon Kleinber and Eva Tardos, Algorithm Design, Addison-Wesley, 2006. (on reserve)
- T. Cormen, C. Leiserson, R. Rivest, and C. Stein, Introduction to Algorithms, 2nd edition, 2001.
- 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.
No comments:
Post a Comment