CSE 521: Design and Analysis of Algorithms (Winter 2017)

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:00-3:45 in CSE 636.
Lectures: Monday - Wednesday 1:30 - 2:50 at EEB 031
Teaching Assistant: Robbie Weber
    Office hours: Tue at 11:00, Thu at 2:00 in CSE 220.

Course evaluation: Homework (~50%), Midterm (~20%), Final project (~30%).
Each student must scribe one lecture. Here is the scribe template file.
Discussion Board


Assignments will be submitted via Canvas.

Notes about the final project

Related Materials

Similar courses at other schools Here is a list of related books
Tentative Schedule:
Lecture Topic Notes Reading Files
Lecture 1
Introduction, Contraction Algorithm pdf MR section 1.1
Lecture 2
Sampling, Concentration Bounds pdf A list of concentration inequalities
Lecture 3
Concentration Bounds, Hash Functions pdf
(01/16/17) No class: Martin Luther King Day
Lecture 4
Hashing Pdf The two tier hashing Algorithm paper
Notes by Jeff Erickson
Notes by Sanjeev Arora
Summer School on Hashing
Lecture 5
Streaming pdf [AMS] paper
Chapter of 1 of Roughgarden's course
Lecture 6
Locally Sensitive Hashing pdf A survey by Bernard Chazelle
Indyk-Motwani's Paper
Charikar's Paper
Data Dependent Hashing for NNS
Lecture 7
Shwartz-Zippel Lemma, Perfect Matching pdf Derandomized Polynomial Identity testing implies Amazing result in Complexity Theory
Harvey's algebraic algorithm
Bipartite matching is in quasi-NC
Lecture 8
Linear Algebra Background, Low Rank Approximation pdf see Trevisan's lecture note for background on spectral theorem
(02/06/17) No class: Due to Snow
Lecture 9
Max cut, Spectral Graph Theory pdf Sections 3.1-3.4 of Hopcroft-Kannan
Column subset selection
Paper 1 Paper 2 on Low rank approximation in Almost linear time
A markov chain algorithm for column subset selection
A theoretical result on nonnegative matrix factorization
Matlab code
Lecture 10
Max Cut, The Laplacian Matrix pdf Hopcroft-Kannan
Chapter 5 of Kannan-Vempala
Goemans and Williamson Approximation Algorithm for maxcut
Lecture 11
Spectral Partitioning, Cheeger's Inequality pdf Trevisan's spectral graph theory course
Spielman's spectral graph theory course
Higher order Cheeger inequalities
k median and k center on planar graphs
Trevisan's lecture notes on log(n) approximation for sparsest cut
(02/20/17) No Class: Presidents Day
Lecture 12
Cheegers Inequality, Power Method pdf Spectral Clustering
My lecture notes on Harder direction of Cheeger's inequality
Lecture 13
Power Method, Random Walks, pdf See here and here for fast Laplacian solvers
See here for applciatons of fast Laplacian solvers in Max-Flow
Graph Draw, Grid, carbon
A zip file of image segmentation files
Lecture 14
Random Walks, Linear Programming pdf An application of random walks in counting
See here and here for applications random walks in local graph clustering
See here for fastest known algorithms for solving LPs
Lecture 15
LP Rounding, MDPs pdf Applications of LPs in Approximation Algorithms
Lecture 16
Duality and Applications