CSE 521: Design and Analysis of Algorithms (Fall 2018)

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 JHN 022
Teaching Assistant: Farzam Ebrahiminejad
    Office hours: Tuesday/Friday 15:00-15:45, CSE 220.

Course evaluation: Homework (~70%), Final project (~30%).
Discussion Board


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
Introduction, Contraction Algorithm pdf MR Section 1.1
Minimum cuts in Near Linear time
Lecture 2
Concentration Bounds pdf MR Sections 3.1,3.2.,3.3
Lecture 3
Strong Concentration Bounds pdf MR Sections 4.1,4.2
Lecture 4
Lecture 5
Streaming pdf Chapter 1 of Roughgarden's Course
AMS paper
Lecture 6
Locally Sensitive Hash Functions pdf A survey by Bernard Chazelle
Indyk-Motwani paper
Data Dependent hashing for NNS
Lecture 7
Curse of Dimensionality, Dimension Reduction pdf Chapter 2 of Foundations of DS
Impossiblity of Dimension Reduction in L1
Lecture 8
Schwartz-Zippel Lemma pdf Derandomized PIT implies Amazing Results
Harvey's algebraic algorithm
Bipartite matching is in quasi-NC
General matching is in quasi-NC
Lecture 9
Linear Algebra Background: SVD, Det, Trace pdf
Lecture 11
Low Rank Approximation pdf Sections 3.1-3.4 of DS
Chapter 4 of Sketching Book
Paper 1, Paper 2 on fast Low rank approximation
A theoretical result on nonnegative matrix factorization
Lecture 12
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
Spectral Graph Theory, Clustering pdf Local Graph Clustering Algorithms
Different Objective fns for Clustering
Lecture 14
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
Power Method, Spectral Sparsification pdf Spectral Sparsification by Effective Resistance
Linear sized Spectral Sparsifiers
Vertex Sparsifiers
My notes on effective resistance
Lecture 16
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
MDPs, Rounding pdf Applications" of LP in Randomized Rounding
Lecture 18
LP Rounding, Duality
Lecture 19
Max-Flow, Min Cut