Advanced Algorithms
CS/CMS 139
Winter 2016




Class: Tuesdays and Thursdays 1-2:30pm, Annenberg 105.
Recitation: TBD.


Tentative schedule


January 5th Probabilistic inequalities and application to streaming algorithms. notes
January 7th Chernoff bound; the power of two choices. notes
January 8th Recitation: Bernstein and other concentration inequalities
January 12th No class (Thomas away). Will find makeup date.
January 14th No class (Thomas away). Will find makeup date.
January 8th Recitation: Estimating higher frequency moments in the data stream model
January 19th The experts/multiplicative weights algorithm and its analysis notes
January 21st Applications of the experts algorithm notes
January 22nd Recitation: Review of linear programming and duality.
January 26th Semidefinite programming notes
January 28th Solving SDPs using multiplicative weights notes
January 29th Recitation: Applications of semidefinite programming in optimization.
February 2nd Fast approximation algorithms for MAXCUT and MAXQP notes
February 4th Dimension reduction notes
February 5th Fast Johnson-Lindenstrauss and applications notes
February 9th Spectral methods: graph properties from the adjacency matrix notes
February 11th Random walks on graphs notes
February 12th Recitation: The spectra of random graphs.
February 16th Volume estimation notes
February 18th Expanders and derandomization notes
February 23rd Solving linear systems of equations notes
January 25th Solving Laplacian systems notes
January 26th Recitation: Derandomization via the method of conditional expectations.
March 1st Spectral sparsifiers notes
March 3rd PAC learning
March 8th Analysis of Boolean functions