UIUC CS 598 (CRN 62819) TOPICS IN ALGORITHMS, Spring 2015

Instructor: Avrim Blum /// Time: Mon, Wed 12:30-1:45, 1304 SC /// Office hours: Wed 4:00-5:00, 3212 SC


Course description: This course will cover a collection of topics in theory and algorithms for analysis of data and networks. Topics will include:

Coursework: Coursework will consist of 5-6 homework assignments, helping with grading of one homework assignment, an optional course project or presentation (can take the place of one homework), plus active participation in class and on the Piazza discussion page (I would like to see at least one comment by each student related to each chapter).

Readings: These readings are from a forthcoming book with John Hopcroft and Ravi Kannan.

Homeworks:

Lectures:
  1. 01/21: [Chapter 2] Getting used to high dimensions, the Perceptron algorithm, basic properties of high-dimensional objects.
  2. 01/26: [Chapter 2] Properties of the d-dimensional ball and Gaussian, selecting from a Gaussian, the Law of Large Numbers.
  3. 01/28: [Chapter 2] Gaussian annulus theorem, tail bounds for sums of random variables with bounded moments, the Johnson-Lindenstrauss Lemma.
  4. 02/02: [Chapter 3] Singular vectors and intro to SVD.
  5. 02/04: [Chapter 3] Continuing with SVD, orthogonality of left singular vectors, power method.
  6. 02/09: [Chapter 3] Power method, Laplacians, PCA.
  7. 02/11: [Chapter 3,6] Mixture of Gaussians, Batch/PAC learning model, Occam's razor.
  8. 02/16: [Chapter 6] Uniform convergence, Regularization, Stochastic Gradient Descent.
  9. 02/18: [Chapter 6] Online mistake bounds; Perceptron, Margins, and Hinge-loss.
  10. 02/23: no class.
  11. 02/25: no class
  12. 03/02: [Chapter 6] Online to Batch conversion, Kernel functions.
  13. 03/04: [Chapter 6] Boosting, Sleeping experts.
  14. 03/09: [Chapter 6] VC-dimension.
  15. 03/11: [Chapter 7] Streaming algorithms 1: counting distinct elements, sampling.
  16. 03/16: [Chapter 7] Streaming algorithms 2: finding heavy hitters, estimating the second moment.
  17. 03/18: [Chapter 7] Length-squared sampling for fast approximate matrix operations. CUR decomposition.
  18. 03/30: [Chapter 7] Finish CUR decomposition.
  19. 04/01: [Chapter 5] Random walks and Markov chains. Fundamental Thm of MCs.
  20. 04/06: [Chapter 5] Random walks and electrical networks, cover times.
  21. 04/08: [Chapter 5] Random walks and electrical networks, cover times, contd.
  22. 04/13: [Chapter 5] Convergence time of random walks on undirected graphs. Rapid mixing.
  23. 04/15: [Chapter 5] Finish rapid mixing. Canonical path method.
  24. 04/20: [Chapter 4] Random graphs and phase transitions. Existence of triangles. 2nd-moment method.
  25. 04/22: [Chapter 4] Random graphs and phase transitions. Diameter at most 2. Connectivity.
  26. 04/27: [Chapter 4] Random graphs and phase transitions. Finish connectivity and isolated vertices. General increasing properties.
  27. 04/29: Resource allocation problems: minimum-congestion routing, offline (Raghavan-Thompson) and online (Awerbuch-Azar-Plotkin).
  28. 05/04: Introduction to Game Theory.
  29. 05/06: Regret minimization, RWM algorithm, Minimax, Internal Regret and Correlated Equilibrium.