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

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: Tue 11:30-12:15, Alle Center 636
Lectures: Tue - Thu 10:00 - 11:20 in Gates Center G01
Teaching Assistants:

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

Assignments

Assignments will be submitted via Gradescope.

Class Mailing list: cse521a_au21

Final Project

Suggestions

Common Knowledge

Related Materials

Similar courses at other schools Here is a list of related books
Inclass Notes in Scribble.

Tentative Schedule:
Lecture Topic Notes Reading Files
Lecture 1
(09/29/2022)
Introduction, Contraction Algorithm pdf MR Section 1.1
Lecture 2
(10/04/2022)
Concentration Bounds pdf MR sections 3.1, 3.2, 3.3
Lecture 3
(10/06/2022)
Strong Concentration Bounds pdf MR sections 4.1, 4.2.
Lecture 4
(10/11/2022)
Hashing pdf Pairwise Independence and Derandomization
Lecture 5
(10/13/2022)
Unbiased Estimators pdf
Lecture 6
(10/18/2021)
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
(10/25/2022)
Dimension Reduction
Johnson Lindenstrauss Transofrm
pdf Chapter 2 of Foundations of DS
Impossiblity of Dimension Reduction in L1
Lecture 9
(10/27/2022)
Schwartz-Zippel Lemma pdf Algebraic Algorithms for Matchings
Lecture 10
(11/01/2022)
Linear Algebra Background: SVD, Det, Trace pdf
Lecture 11
(11/03/2022)
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
(11/08/2022)
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
(11/10/2022)
Spectral Graph Theory, Clustering pdf
Lecture 14
(11/17/2022)
Lecture 15
(11/22/2022)
Power Method pdf PCA
Graph Drawing
(11/24/2021) No class: Thanks Giving
Lecture 16
(11/29/2022)
Linear Programming and the Ellipsoid Method pdf
Lecture 17
(12/01/2022)
LP and SDP Rounding
Lecture 18
(12/06/2022)
Duality, LP Rounding
Lecture 19
(12/08/2022)
Submodular Maximization Influence Maximization Problem