We will study the design and analysis of algorithms from a modern perspective with a particular focus on techniques that find use in many subfield of computer science. The modern perspective means that there will be extensive use of randomization, linear algebra, and optimization.
Topics will include randomized algorithms, streaming, advanced data structures, dimensionality reduction, clustering, low rank approximation, markov decision processes, linear programming, etc.
Administrative Information
Instructor: Shayan Oveis Gharan
Office Hours: Fri 2:503:35 in CSE 636.
Lectures: Monday  Fri 1:30  2:50 at EE 037
Teaching Assistants: Dorna Abdolazimi, Kuikui Liu
Office hours: Tuesday 12:301:30 (Dorna), Wednesday 3:004:00 (Kuikui) at CSE1 220 .
Course evaluation: Homework (~80%), Final project (~20%).
Discussion Board
Assignments
 Assignment1, due Friday October 11th, 6:00 PM
Inputs: c1.in, c2.in, c3.in
 Assignment2, due Oct 27th, 6:00 PM, Inputs: lsh1.in, lsh2.in, lsh3.in
 Assignment3, due Nov 10th, 6:00 PM
 Assignment4, due Nov 25th, 6:00 PM
 Assignment5, due Dec 6th, 6:00 PM
Assignments will be submitted via Canvas.
Final Project
Here are some notes about the final project.
Suggestions
Related Materials
Similar courses at other schools
Here is a list of related books


Tentative Schedule:
Lecture  Topic  Notes  Reading  Files 
Lecture 1 (09/27/2019)  Introduction, Contraction Algorithm 
pdf  MR Section 1.1 Minimum cuts in Near Linear time  
Lecture 2 (09/30/2019)  Concentration Bounds 
pdf  MR Sections 3.1,3.2.,3.3  
Lecture 3 (10/04/2019)  Strong Concentration Bounds 
pdf  MR Sections 4.1,4.2  
Lecture 4 (10/7/2019)  Hashing 
pdf  Pairwise Independence and Derandomization  
Lecture 5 (10/11/2019)  Streaming 
pdf  Chapter 1 of Roughgarden's Course AMS paper  
Lecture 6 (10/14/2019)  Locally Sensitive Hash Functions 
pdf  A survey by Bernard Chazelle IndykMotwani paper Data Dependent hashing for NNS  
Lecture 7 (10/18/2019)  Curse of Dimensionality, Dimension Reduction 
pdf  Chapter 2 of Foundations of DS Impossiblity of Dimension Reduction in L1  
Lecture 8 (10/21/2019)  Curse of Dimensionality Continued 
  
Lecture 9 (10/25/2019)  SchwartzZippel Lemma  pdf  Derandomized PIT implies Amazing Results
Harvey's algebraic algorithm
Bipartite matching is in quasiNC
General matching is in quasiNC
 
Lecture 10 (10/28/2019)  Linear Algebra Background: SVD, Det, Trace 
pdf   
Lecture 11 (11/01/2019)  Low Rank Approximation 
pdf  Sections 3.13.4 of DS Chapter 4 of Sketching Book
Paper 1, Paper 2 on fast Low rank approximation A theoretical result on nonnegative matrix factorization  compressimage.m einstein.jpg 
Lecture 13 (11/08/2019)  Spectral Graph Theory 
pdf  Low Rank Approx for Maxcut on Sprase Graphs Planted Partitioning using Low Rank Approx Goemans and Williamson's Approx Alg for Maxcut
Different Objective fns for Clustering
Approx Maxcut on Expander Graphs
 
(11/11/2019)  No Class: Veterans Day 
Lecture 14 (11/15/2019)  Cheegers Inequlity, Spectral Clustering 
pdf 
See here for proof of Hard Dir of Cheeger
Local Graph Clustering Algorithms
Higher Order Cheeger Inequalities
Spectral Clustering


Lecture 15 (11/18/2019)  Spectral Sparsification 
pdf 
Random graphs are almost Ramanujan
 graphdrawing.tar
imseg.tar 
Lecture 16 (11/22/2019)  Linear Modeling 
pdf 
Goemans Lecture notes on Ellipsoid algorithm
Faster Algorithms for solving LPs
 
Lecture 17 (11/25/2019)  MDPs, LP Rounding 
pdf  Boyd's course on Convex Optimization  
(11/29/2019)  No Class: Thanks Giving Day 
Lecture 18 (12/02/2019)  LP Rounding, Duality 
pdf  Applications" of LP in Randomized Rounding  
Lecture 19 (12/06/2019)  Duality, Submodular Maximization 
  
