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

We will study the design and analysis of algorithms from a modern perspective with a particular focus on techniques that find use in many subfields 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: M 12:30-1:20, zoom link.
Lectures: Mon - Wed 1:30 - 2:50 in ECE 003, zoom link: https://washington.zoom.us/j/98169099727
Teaching Assistants:

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


Assignments will be submitted via Gradescope.

Class Mailing list: cse521a_au21

Final Project


Common Knowledge

Related Materials

Similar courses at other schools Here is a list of related books
Inclass [Lecture 1-4] Notes in Scribble.
Inclass [Lecture 5-9] Notes in Scribble.
Inclass [lecture 10-13] Notes in Scribble.
Inclass [lecture 16-19] Notes in Scribble.

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
Unbiased Estimators pdf
Lecture 6
Streaming / Locally Sensitive Hash Functions pdf Chapter 1 of Roughgarden's Course
AMS paper
A Survey by Bernard Chazelle
Indyk-Motwani Paper
Data Dependent hashing for NNS
Lecture 7-8
Dimension Reduction
Johnson Lindenstrauss Transofrm
pdf Chapter 2 of Foundations of DS
Impossiblity of Dimension Reduction in L1
Lecture 9
Schwartz-Zippel Lemma pdf Algebraic Algorithms for Matchings
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
Lecture 12
Max Cut Problem pdf Low rank approx for Maxcut on Sparse Graphs
Planted Partitioning using Low rank Approximation
Goemans and Williamson Approximation Algorithm for Maxcut
Lecture 13
Spectral Graph Theory, Clustering pdf
Lecture 14
Lecture 15
Lecture 16
Spectral Sparsification
(11/24/2021) No class: Thanks Giving
Lecture 17
Linear Programming and SDP pdf
Lecture 18
LP and SDP Rounding
Lecture 19
Duality, LP Rounding pdf
Lecture 20
Submodular Maximization Influence Maximization Problem