CS 6550 (Algorithms), Fall 2009

Course Information:

Professor: Dana Randall
Lectures: TTh 12:00-1:30, Room CCB 102
Office Hours: T 1:30-2:30, W 2:00-3:00, Room KACB 2140
Recommended (Optional!) Texts:

• Algorithm Design by Kleinberg and Tardos
• Randomized Algorithms by Motwani and Raghavan
• Introduction to Algorithms by Cormen, Leiserson, Rivest and Stein
  

Homeworks: Approximately every two weeks.
Exam: Take home final.
______________________________
Announcements

• Nov 17: The take home final is now posted. It is due by the beginning of class on December 3rd. Please keep the lecture notes coming to me!
• 10/15 We are canceling class on October 27 so that interested students can attend FOCS. Everyone's presentation (after the first 2) has been moved down to the next lecture. Below please see the corrected schedule. Let me know asap if there are any problems!!!
• 10/15 Homework 4 has been assigned. Please notice that there is plenty of time to do it! (Due Nov 3.)
• 10/14: Please aim to get me drafts of your lecture notes by the end of October. (Of course the first 4 lectures need to come to me much sooner (asap) so that we can make them available to students by the time of your lecture.) 1st DRAFTS OF LECTURE NOTES MUST COME TO ME 2 WEEKS BEFORE YOUR LECTURE!!!
• 9/22: The assignment of presentation topics is now posted. Please see below for the assignment and the schedule (listed among the lecture notes). Let me know NOW if this schedule does not work for you for some reason. On Thursday you can begin to identify your partner in order to exchange email and start thinking about your plan of attack!
• 9/11: Presentation topics are now available (see below). Each topic has two examples of papers that might start you off designing your lecture. You do not pick a paper from the topics, but the whole topic, which may or may not be based on the papers I suggested. You need to submit your top 3 topic preferences by Thursday, September 17. Also include any scheduling issues I should be aware of.
  
  Homework 2 is due Sept 22. Tiny typo corrected in question 5, if you already downloaded it.

Final

• Take home final Due before class on 12/3/09. Please do 8 out of 9 and indicate which you are skipping. You must work alone. Good luck!

Lectures

• Approximation algorithms:
  
  • Aug 18: Vertex cover, set cover, randomized rounding (CMU)
  • Aug 20: VC, set cover, TSP (Berkeley)
  • Aug 25,27: Knapsack (Berkeley)
• Randomized algorithms:
  
  • Sep 1: k-wise independence, linearity of expectation, quicksort
  • Sep 3: Min-cut
  • Sep 8: The occupancy problem, Markov's inequality, Chebyshev's inequality
  • Sep 10: Chernoff bounds and The power of two: balls and bins
• On-line Algorithms:
  
  • Sep 15: Intro to on-line algs; paging
  • Sep 17: Randomized paging
  • Sep 22: The k-server problem
  • Sep 24: Randomized ski-rental
• Geometric algorithms:
  • Sep 29, Oct 1: Finding convex hulls
  • Oct 8, 13: Voronoi regions (see also notes by David Mount) and Delaunay triangulations
• Overview of Markov Chains
  • Oct 15: Tutorial slides
• Student presentations:
  • Oct 20: Property Testing -- Ning Tan and Steven Ehrlich
  • Oct 22: Bloom Filters and Hashing -- Wei Jin and Alessio Guerrieri
  • Oct 27: CLASS CANCELED SO WE CAN ATTEND FOCS!!
  • Oct 29: Randomized Rounding and Semi-Definite Programming -- Qie He and Abhinav Shantanam
  • Nov 3: Multicommodity Flow -- Ding Ding (Michael) Xu and Sarah Fletcher
  • Nov 5: Oblivious Routing (ppt slides) -- Rajiv Iyer and Tuba Yilmaz (and additional slides)
  • Nov 10: PTAS for Euclidean TSP -- Yaxian Li and Sethuraman Krishnan
  • Nov 12: The k-server Problem -- Ruidong Wang and Andrew Crowe
  • Nov 17: Spectral Analysis of Data -- Sarah Miracle and Hong Yu
  • Nov 19: Estimating the Volume of a Convex Body -- Prateek Bhakta and Charlie Morn
  • Nov 24: Expanders, s-t Connectivity and Log-Space -- Spencer Backman and Akash Kumar
  • Dec 1: Preferential Attachment and Scale Free Graphs (w/ Power Laws) -- Luyi Gui and Pramod Gupta
• Additional topics TBD:
  • Dec 3:
  
  
  Homeworks
  • Homework 1 -- Due Thursday, Sept 3.
    Hw 1 Solution Thanks to Qie He and Yaxian Li for grading this! They pointed out a couple of typos in the posted solutions.
    
  • Homework 2 -- Due Tuesday, Sept 22. (The last one is fun to think about!)
    Hw 2 Solution Thanks to Tuba Yilmaz and Akash Kumar for grading. And here's a solution to the 2^n coins generalization due to Steven Ehrlich.
  • Homework 3 -- Due Thursday, Sept 8.
    Hw 3 Solution Thanks to Sarah Fletcher and Michael Xu for grading.
  • Homework 4 -- Due Tuesday, November 3.
    

Suggested Paper and Presentation topics and examples of papers you might choose to read for these 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 8 or 13. 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. If you need more time and want to present later in the semester, please let me know asap.

Your finalized lecture notes must be complete (including editing changes suggested by me or a proofreader from the class) before your lecture. Use the latex template below for a starting point. Instructions for opening links through the library are also below.

• 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.
  
  
• 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.
  
  
• 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.
  
  
• 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.
  
  
• 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.
  
  
• Property testing
  • O. Goldreich and L. Trevisan, Three theorems regarding testing graph properties. Random Structures and Algorithms, 2003.
  
  
• 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.
  
  
• 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.
  
  
• 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.
  
  
• 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.
  
  
• 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.
  
  
• 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.
  
  
• Bloom filters and hashing
  • A. Kirsch and M. Mitzenmacher. Less hashing, same performance: building a better Bloom filter. ESA 2006.
  • S. Lumetta and M. Mitzenmacher. Using the power of two choices to improve Bloom filters. Internet Mathematics, Vol 4, 17-33, 2009.
    

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)

• LaTeX Documentation,
• Help On LaTeX Commands