Online Algorithms

Instructor: Adam Kalai

CMSC 39600-1
Topics in Theoretical Computer Science

Mon, Wed 4:30-5:20. Fridays 3:30-4:20. (If there is any difficulty with this time change, please email me.) Ryerson 276

Course information
The final is available now. After you download it, you have 1 day (24 hours) to do it and turn in your answers. You are under the honor code to obey these rules. If you would like to turn in a written solution, you should get it into my mailbox at TTI by Monday, December 6th, 2pm. Otherwise, you must mail an electronic copy to me by December 12th. After you have turned in the final, you may take a look at the solutions.

Homework
  1. 10/1. Homework 1. Due 10/8.
  2. 10/11. Homework 2. Due 10/18.
  3. 10/20. Homework 3. Due 10/27.
  4. 10/27. Homework 4. Due 11/4.
  5. 11/11. Homework 5. (Revised 11/15) Due 11/22.
  6. 11/21. Homework 6. Due 11/30.

Lectures and notes
  1. 9/27. Intro. Competitive ratio. Rent or buy, finding a hole in the fence, move to front
  2. 9/29. Frequency count accounting.
  3. 10/1. Randomized Frequency Count.
  4. 10/4. Splay Trees. Powerpoint slides by Haim Kaplan. Perhaps more helpful Scribe notes from David Karger's class. Original paper by Sleator and Tarjan. Dynamic optimality -- almost by Erik D. Demaine, Dion Harmon, John Iacono, and Mihai Patrascu.
    10/5. Online algorithms lecture on TUESDAY at 12:15 at TTI. (lunch provided) Slides, paper.
    10/6. No class due to Cynthia Dwork's cryptography lecture, 4pm Ryerson 251.
  5. 10/8. Zinkevich's analysis of online gradient descent. His original paper.
  6. 10/11. Proof of the min-max theorem. Weighted majority algorithm.
  7. 10/13. Applications of weighted majority and Hannan-style algorithms.
  8. 10/15. Hannan-style algorithms.
  9. 10/18. The multi-armed bandit problem.
  10. 10/20. The multi-armed bandit problem, continued. This is based on a paper by R. Weber: On the Gittins index for multiarmed bandits. Ann. Appl. Prob. 2, 1024-33, 1992. Feel free to email me for a copy.
  11. 10/22. Bandit extensions to online optimization. These are based on two papers: B. Awerbuch and R. Kleinberg, Near-Optimal Adaptive Routing: Shortest Paths and Geometric Generalizations. (This contains the definition and algorithms for Barycentric spanners.) B. McMahan and A. Blum, Online Geometric Optimization in the Bandit Setting Against an Adaptive Adversary. (This contains the one-point exploration estimates.)
  12. 10/25. Continued.
  13. 10/27. Caching. Scribe notes from Bartal's class.
  14. 10/29. No class, due to anticipated strike.
  15. 11/1. Caching continued. More scribe notes from Bartal's class.
  16. 11/3. K-server problem: double coverage alg. More scribe notes from Bartal's class.
  17. 11/5. K-server problem: Work-function algorithm. More scribe notes from Bartal's class.
  18. 11/8. K-server problem: Analysis. See paper for details.
  19. 11/10. Loose ends and planning. See also Avrim's notes on the K-server problem.
  20. 11/12. Universal portfolios (and relationship to compression). Here is a nice web page on the topic. This is a paper.
  21. 11/15. Online data compression. Dynamic Huffman codes.
  22. 11/17. More on compression, universal portfolios, and online coding. See descriptions of Dynamic Huffman Codes, a nice page on various codes, and Online Language Models.
  23. 11/19. Class cancelled for talk at TTI.
  24. 11/22. Lempel Ziv.
  25. 11/24. Class cancelled for Thanksgiving preparations.
  26. 11/26. Class cancelled for Thanksgiving digesting.
  27. 11/29. Winnow and Perceptron algorithms.

Handouts and Readings

Research papers and related lecture notes.