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: Mon 11:30-12:30, Allen Center 636
Lectures: Mon-Wed 10:00 - 11:20 in Gates 04
Teaching Assistants:
- Arvin Sahami, .
- Dante Tjowasi, Office hour: Tuesdays 10:00-10:50, Gates 150.
Discussion Board
Assignments
- Assignment-1, due Wednesday October 08th, 11:59 PM
- Assignment-2, due Wednesday October 15th, 11:59 PM
Class Mailing list: cse521a_au23
Common Knowledge
Related Materials
Similar courses at other schools- Sketching Algorithms by Jelani Nelson
- Advanced Algorithms by Sanjeev Arora
- Computer Science Theory for the Information Age by Venkatesan Guruswami and Ravi Kannan
- Lecture notes on Graph Partitioning and Spectral Methods by Luca Trevisan
- Randomized Algorithms by Rajeev Motwani and Prabhakar Raghavan
- Probability and Computing: Randomzied Algorithms and Probabilistic Analysis by Michael Mitzenmacher and Eli Upfal
- Foundations of Data Science by John Hopcroft and Ravi Kannan
- Spectral Algorithms by Ravi Kannan and Santosh Vempala
- Sketching as a Tool for Numerical Linear Algebra by David Woodruff
Tentative Schedule:
| Lecture | Topic | Notes | Reading | Files |
|---|---|---|---|---|
| Lecture 1 (09/24/2025) | Introduction, Contraction Algorithm | MR Section 1.1 | ||
| Lecture 2 (09/29/2025) | Concentration Bounds | pdf, video | MR sections 3.1, 3.2, 3.3 | |
| Lecture 3 (10/01/2025) | Strong Concentration Bounds | pdf, video | MR sections 4.1, 4.2. | |
| Lecture 4 (10/06/2025) | Hashing | pdf, video | Pairwise Independence and Derandomization | |
| Lecture 5 (10/08/2025) | Unbiased Estimators | pdf,video | ||
| Lecture 6 (10/13/2025) | Streaming / Locally Sensitive Hash Functions | pdfvideo-1, video2 | 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/20/2025) | Dimension Reduction Johnson Lindenstrauss Transform | Chapter 2 of Foundations of DS Impossiblity of Dimension Reduction in L1 | ||
| Lecture 9 (10/22/2025) | Schwartz-Zippel Lemma | Algebraic Algorithms for Matchings | ||
| Lecture 10 (10/27/2025) | Linear Algebra Background: SVD, Det, Trace | |||
| Lecture 11 (10/29/2025) | Low Rank Approximation | Sections 3.1-3.4 of DS Chapter 4 of Sketching Book Paper 1, Paper 2 on fast low rank approximation | ||
| Lecture 12 (11/03/2025) | Max Cut Problem | Low rank approx for Maxcut on Sparse Graphs Planted Partitioning using Low rank Approximation Goemans and Williamson Approximation Algorithm for Maxcut | ||
| Lecture 13 (11/05/2025) | Spectral Graph Theory, Clustering | |||
| Lecture 14 (11/10/2025) | ||||
| Lecture 15 (11/12/2025) | Power Method | PCA Graph Drawing | ||
| Lecture 16 (11/17/2025) | Linear Programming and the Ellipsoid Method | |||
| Lecture 17 (11/19/2025) | LP and SDP Rounding | |||
| Lecture 18 (11/24/2025) | Duality | |||
| (11/26/2025) | No class: Thanks Giving | |||
| Lecture 19 (12/01/2025) | Submodular Maximization | Influence Maximization Problem | ||
| Lecture 20 (12/03/2053) | Multiplicative Weight Update Algorithm | |||