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: Mon, Wed 3:003:45 in CSE 636.
Lectures: Monday  Wednesday 1:30  2:50 at JHN 022
Teaching Assistant: Farzam Ebrahiminejad
Office hours: Tuesday/Friday 15:0015:45, CSE 220.
Course evaluation: Homework (~70%), Final project (~30%).
Discussion Board
Assignments
 Assignment1, due Monday October 15th, 12:00 PM
Inputs: b0.in, b1.in, b2.in, b3.in
 Assignment2, due Oct 29th, Inputs: j0.in, j1.in, j2.in, j3.in, j4.in jacc.cpp
 Assignment3, due Nov 12th.
 Assignment4, due Dec 5th.
Assignments will be submitted via Canvas.
Final Project
Here are some notes about the final project.
Suggestions
Common Knowledge
Related Materials
Similar courses at other schools
Here is a list of related books


Tentative Schedule:
Lecture  Topic  Notes  Reading  Files 
(09/26/2018)  No Class: Conference 
Lecture 1 (10/01/2018)  Introduction, Contraction Algorithm 
pdf  MR Section 1.1 Minimum cuts in Near Linear time  
Lecture 2 (10/03/2018)  Concentration Bounds 
pdf  MR Sections 3.1,3.2.,3.3  
Lecture 3 (10/08/2018)  Strong Concentration Bounds 
pdf  MR Sections 4.1,4.2  
Lecture 4 (10/10/2018)  Hashing 
  
Lecture 5 (10/15/2018)  Streaming 
pdf  Chapter 1 of Roughgarden's Course AMS paper  
Lecture 6 (10/17/2018)  Locally Sensitive Hash Functions 
pdf  A survey by Bernard Chazelle IndykMotwani paper Data Dependent hashing for NNS  
Lecture 7 (10/22/2018)  Curse of Dimensionality, Dimension Reduction 
pdf  Chapter 2 of Foundations of DS Impossiblity of Dimension Reduction in L1  
Lecture 8 (10/24/2018)  SchwartzZippel Lemma  pdf  Derandomized PIT implies Amazing Results
Harvey's algebraic algorithm
Bipartite matching is in quasiNC
General matching is in quasiNC
 
Lecture 9 (10/31/2018)  Linear Algebra Background: SVD, Det, Trace 
pdf   
Lecture 11 (11/05/2018)  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 12 (11/07/2018)  Max Cut, 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  
(11/12/2018)  No Class: Veterans Day 
Lecture 13 (11/14/2018)  Spectral Graph Theory, Clustering 
pdf 
Local Graph Clustering Algorithms
Different Objective fns for Clustering  graphdrawing.tar
spectralclusterin.tar 
Lecture 14 (11/19/2018)  Spectral Clustering 
pdf 
Spectral Clustering
Approx Maxcut on Expander Graphs
Higher Order Cheeger Inequalities
See here for proof of Hard Dir of Cheeger
 
Lecture 15 (11/21/2018)  Power Method, Spectral Sparsification 
pdf  Spectral Sparsification by Effective Resistance
Linear sized Spectral Sparsifiers
Vertex Sparsifiers
My notes on effective resistance  
Lecture 16 (11/26/2018)  Linear Modeling 
pdf  Random graphs are almost Ramanujan
Boyd's course on Convex Optimization
Goemans Lecture notes on Ellipsoid algorithm
Faster Algorithms for solving LPs
 
Lecture 17 (11/28/2018)  MDPs, Rounding 
pdf  Applications" of LP in Randomized Rounding  
Lecture 18 (12/03/2018)  LP Rounding, Duality 
  
Lecture 19 (12/05/2018)  MaxFlow, Min Cut 
  
