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

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:50-3:35 in CSE 636.
Lectures: Monday - Fri 1:30 - 2:50 at EE 037
Teaching Assistants: Dorna Abdolazimi, Kuikui Liu
    Office hours: Tuesday 12:30-1:30 (Dorna), Wednesday 3:00-4:00 (Kuikui) at CSE1 220 .

Course evaluation: Homework (~80%), Final project (~20%).
Discussion Board


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
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
Hashing pdf Pairwise Independence and Derandomization
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
Curse of Dimensionality Continued
Lecture 9
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 10
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 13
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
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
Spectral Sparsification pdf Random graphs are almost Ramanujan
Lecture 16
Linear Modeling pdf Goemans Lecture notes on Ellipsoid algorithm
Faster Algorithms for solving LPs
Lecture 17
MDPs, LP Rounding pdf Boyd's course on Convex Optimization
(11/29/2019) No Class: Thanks Giving Day
Lecture 18
LP Rounding, Duality pdf Applications" of LP in Randomized Rounding
Lecture 19
Duality, Submodular Maximization