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:
- Farzam Ebrahiminejad, Office hour: Tue 11:00-11:50 in zoom
- Xinzhi Zhang, Office hour: Thu 3:00-3:50 in zoom
Discussion Board
Assignments
- Assignment-1, due Sunday October 17th, 11:59 PM Inputs for P1: kar-1.in, kar-2.in, kar-3.in
- Assignment-2, Input for P4 reachable.in, due Nov 2nd, 11:59 PM,
- Assignment-3, due Nov 19th, 11:59 PM, jecond.jpg
- Assignment-4, due Dec 9th, 11:59 PM
Class Mailing list: cse521a_au21
Final Project
Suggestions- Beating CountSketch for Heavy Hitters
- Sprase Johnson Lindenstrauss
- How Bad is Selfish Routing
- Bipartite Matching is in Quasi NC
- Low Rank Approximation and Regression in Input Sparsity Time
- Low Rank Approximation for PSD
- Solving Laplacian Linear Systems by Approximate Gaussian Elimination
- Correlation Clusering
- Graph Clustering using Random Walks
- Approximation Algorithms for Hierarchical Clustering
- Linear size Spectral Sparsifiers
- An Improved Distributed Algorithm for Maximal Independent Set
- Finding Maximum Flow using Electrical Flows
- Perfect Matchings in O(n log n) Time in Regular Bipartite Graphs
- Outcome Indistinguishability
- Parallel Graph Connectivity in Log Diameter Rounds
- Approximation Algorithms for Unconstrained Submodular Maximizaiton
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
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 (09/29/2021) | Introduction, Contraction Algorithm | MR Section 1.1 Minimum cuts in Near Linear time | ||
| Lecture 2 (10/04/2021) | Concentration Bounds | MR sections 3.1, 3.2, 3.3 | ||
| Lecture 3 (10/06/2021) | Strong Concentration Bounds | MR sections 4.1, 4.2. | ||
| Lecture 4 (10/11/2021) | Hashing | Pairwise Independence and Derandomization | ||
| Lecture 5 (10/13/2021) | Unbiased Estimators | |||
| Lecture 6 (10/18/2021) | Streaming / Locally Sensitive Hash Functions | 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/2021) | Dimension Reduction Johnson Lindenstrauss Transofrm | Chapter 2 of Foundations of DS Impossiblity of Dimension Reduction in L1 | ||
| Lecture 9 (10/27/2021) | Schwartz-Zippel Lemma | Algebraic Algorithms for Matchings | ||
| Lecture 10 (11/01/2021) | Linear Algebra Background: SVD, Det, Trace | |||
| Lecture 11 (11/03/2021) | 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/08/2021) | 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/10/2021) | Spectral Graph Theory, Clustering | |||
| Lecture 14 (11/15/2021) | ||||
| Lecture 15 (11/17/2021) | ||||
| Lecture 16 (11/22/2021) | Spectral Sparsification | |||
| (11/24/2021) | No class: Thanks Giving | |||
| Lecture 17 (11/29/2021) | Linear Programming and SDP | |||
| Lecture 18 (12/01/2021) | LP and SDP Rounding | |||
| Lecture 19 (12/06/2021) | Duality, LP Rounding | |||
| Lecture 20 (12/08/2021) | Submodular Maximization | Influence Maximization Problem | ||