Course Information:
Lectures: TTh 1:30-3:00, Room ES&T L1255Recommended (Optional!) Texts:
- Randomized Algorithms by Motwani and Raghavan
- Introduction to Algorithms by Cormen, Leiserson, Rivest and Stein
TA: Shiva Kintali (kintali@gmail.com) , Klaus 2210, Office hours: W 2:00-4:00
Homeworks: Approximately every two weeks.
Exam: Take home final.
Announcements
- 8/23: There will not be a diagnostic quiz.
- 8/30: Homework 1 assigned, below. Due Sept 6.
- 9/10: See initial list of presentation topics below.
- 9/13: Homework 2 below. Please get me your project preferences asap!
- 9/18: Project assignments below.
- Please let me know asap if the schedule poses a problem for you.
- I expect to get drafts of your lecture notes by mid-October unless you are giving one of the first 3 lectures in which case I need them sooner!
- Polished versions of your notes are due before your lectures, so do leave ample time for Shiva and me to go over them before they are posted.
- 10/16: Homework 3 below. Please keep drafts coming and set up meetings if you need to.
- 10/30: Several students asked for extensions on Homework 3 until Thursday, so I am extending it for everyone. Hope this helps!
- 11/8: Class cancelled due to the Ford building being blown up. Instead we will postpone the class on property testing to November 15th (instead of my lecture on sampling colorings).
- 11/13: Please note the change to the schedule for the remainder of the lectures.
- 11/20: Final assigned. Due December 6. Get it here: FINAL EXAM
- 12/5: Extension on Final: The final is now due by noon on Friday 12/7 (under my office door).
Lectures
- Approximation algorithms:
- Aug 21: Vertex cover, set cover, randomized rounding (CMU)
- Aug 23, 28: VC, set cover, TSP (Berkeley)
- Aug 30: Knapsack (Berkeley)
- Randomized algorithms:
- On-line Algorithms:
- Sep 18: Intro to on-line algs; paging
- Sep 20: Randomized paging
- Sep 25: The k-server problem
- Sep 27: Randomized ski-rental
- Geometric algorithms:
- Oct 2, 4: Finding convex hulls
- Oct 11: Voronoi regions (see also notes by David Mount)
- Oct 16: Delaunay triangulations
- Student presentations (TBA)
- Oct 18: Multicommodity Flow
- Oct 23: Oblivious Routing Schemes
- Oct 25: SDP and Maxcut
- Oct 30: PTAS for Euclidean TSP
- Nov 1: The k-server problem
- Nov 6: Generalizations of ski-rental
- Nov 13: Spectral analysis of data
- Nov 15: Property testing
- Nov 20: Estimating the volume of a convex body
- Nov 29: st-connectivity in logspace
- Oct 18: Multicommodity Flow
Homeworks
- Homework 1 -- Due Thursday, Sept 6.
- Solution
- Homework 2 -- Due Tuesday, Sept 25.
- Solution
- Homework 3 -- Due Tuesday, Oct 30.
- Solution
- FINAL -- Due Thursday, December 6
(in case you missed it up above in the announcments!).
Suggested Paper and Presentation topics
Here is an initial list of presentation topics. Please email me your top 3 preferences (and any constraints on presentation times) by September 17. Presentations will (probably!) start October 18. I realize that some of these links do not access the whole paper -- do your own google searches on the titles or find the conference proceedings or journals if you want the papers.
Outlines/drafts of your lecture notes are due by mid-October, although the first couple of lectures will be due very early October.
Your finalized lecture notes must be complete (including editing changes suggested by me and/or Shiva) before your lecture. Use the latex template below for a starting point.
Instructions for opening links through the library are below, with thanks to Jessica!
- October 18: Kael Stilp and Jessica Heier
Multicommodity flow
- Tom Leighton and Satish Rao, Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms. JACM 1999.
- C. Chekuri, S. Khanna, and B. Shephard, The all or nothing multicommodity flow problem. STOC 2004.
- October 23: Karthekeyan Chadrasekaran and Johannes Schuett
Oblivious routing schemes
- H. Racke, Minimizing congestion in general networks. FOCS 2002.
- M. Bienkowski, M. Korzeniowski and H. Racke, A practical algorithm for constructing oblivous routing schemes. SPAA 2003.
- October 25: Amanda Pascoe and Noah Streib
Randomized rounding and semi-definite programming
- M. Goemans and D. Williamson, Improved approximation algorithms for maximum cut and satisfiability problems using semi-definite programming. JACM, 1995.
- D. Karger, R. Motwani and M. Sudan, Approximate graph coloring by semidefinite programming. JACM, 1998.
- October 30: Kate Abercrombie and Justin Cranshaw
PTAS for Euclidean TSP- S. Arora, Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems. JACM, 1998.
- A. Dumitrescu and J. Mitchell, Approximation algorithms for TSP with neighborhoods in the plane. J. Algs., 2003.
- November 1: Lei Wang and Christopher Breaux
The k-server problem
- E. Koutsoupias, C. Papadimitriou, The k-server conjecture JACM, 1995.
- Y. Bartal and E. Grove, The harmonic k-server algorithm is competitive. JACM, 2000.
- November 6: Ogechi Nnadi and David Rutter
Generalizations of ski-rental
- A. Karlin, C. Kenyon, D. Randall, Dynamic TCP acknowledgement and other stories about $e/(e-1)$. Algorithmica, 2003.
- November 13: Ashish Sangwan and Arvind Batra
Spectral analysis of data
- J. Kleinberg, Authoritative sources in a hyperlinked environment. SODA.
- Y. Azar, A. Fiat, A. Karlin, F. McSherry, J. Saia, Spectral analysis of data. STOC 2001.
- November 15: Brent Myers, Nathan Chenette and Hari Prasad
Property testing
- O. Goldreich and L. Trevisan, Three theorems regarding testing graph properties. Random Structures and Algorithms, 2003.
- November 20: Alejandro Toriello and Daniel Dadush
Estimating the volume of a convex body
- M. Dyer, A. Frieze and R. Kannan, A random polynomial time algorithm for approximating the volume of convex sets.JACM, 1991.
- R. Kannan, L. Lovasz and M. Simonovits, RSA, 1997.
- November 27: me
Markov chains for sampling k-colorings
- M. Jerrum, A very simple algorithm for estimating the number of k-colourings of a low-degree graph RSA 1995.
- D. Randall, Mixing STOC 2003.
- November 29: Linji Yang and Luke Postle
Expanders, ST-connectivity, and log-space
- O. Reingold, S. Vadhan and A. Wigderson, Entropy waves, the zig-zag product, and new constructions of constant-degree expanders. FOCS 2000.
- O. Reingold, Undirected ST-connectivity in log-space. STOC 2005.
- December 4: Tongqing Qiu and Andrey Kislyuk
Power-law degree distributions- A. Fabrikant, E. Koutsoupias, C. Papadimitiou, Heuristically optimized trade-offs: a new paradigm for power laws in the internet. Proc. 29th International Colloquium on Automata, Languages and Programming, 2002.
- D. Achlioptas, A. Clauset, D. Kempe, C. Moore, On the bias of traceroute sampling: or, power-law degree distributions in regular graphs. STOC 2005.
- December 6: Nan Hua and Nishant Mehta
Preferential attachment and scale-free graphs
- R. Kumar, P. Raghavan, S. Rajagopalan, D. Sivakumar, A. Tomkins, E. Upfal, Stochastic models for the web graph. FOCS 2000.
- M. Mihail, C. Papadimitriou, A. Saberi, On certain connectivity properties of the internet topology. FOCS 2003.
Instructions for opening these links:- 1. Start from www.library.gatech.edu.
- 2a. If specific journal is known, click on ejournals link from the library homepage and follow basic instructions from there. (E.g., if you want any proceeding or journal article from ACM, searching by title for "ACM" and then clicking "Find it @GT" will take you to a link for the ACM portal, possibly after you enter your GT id and password.)
- 2b. If the specific journal is not known, click on Articles (Databases) from the library homepage. A good one to use is Compendex (search by database name to get it.) After entering GT id and password, search by author, title or keyword.
THE LATEX TEMPLATE (for writeups on presentations)