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:
- Dorna Abdolazimi, Office hour: Wed 12:30-1:20, CSEII 150
- Artin Tajdini, Office hour: Thu 1:00-1:50 in CSEI 220
Discussion Board
Assignments
- Assignment-1, due Sunday October 16th, 11:59 PM Inputs for P1: karger-1, karger-2, karger-3
- Assignment-2 due OCt 30th, 11:59 PM, inputs for problem 5: stream-1.in, stream-2.in, stream-3.in
- Assignment-3, due Nov 8th, 11:59 PM.
- Assignment-4, due Nov 26th, 11:59 PM, hidden1.in, hidden1.out
- Assignment-5, due Dec 9th, 11:59 PM.
Class Mailing list: cse521a_au21
Final Project
Suggestions- A Note on a Recent Algorithm for Minimum Cut
- Beating CountSketch for Heavy Hitters
- Sprase Johnson Lindenstrauss
- 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
- Low-rank approximation with 1/eps^1/3 matrix-vector products
- Graph Clustering using Random Walks
- Approximation Algorithms for Hierarchical Clustering
- Linear size Spectral Sparsifiers
- Authoritative Sources in a Hyperlinked Environment
- 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
- Simple Constant-Factor Approximation to Edit Distance
- 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
Tentative Schedule:
| Lecture | Topic | Notes | Reading | Files |
|---|---|---|---|---|
| Lecture 1 (09/29/2022) | Introduction, Contraction Algorithm | MR Section 1.1 | ||
| Lecture 2 (10/04/2022) | Concentration Bounds | MR sections 3.1, 3.2, 3.3 | ||
| Lecture 3 (10/06/2022) | Strong Concentration Bounds | MR sections 4.1, 4.2. | ||
| Lecture 4 (10/11/2022) | Hashing | Pairwise Independence and Derandomization | ||
| Lecture 5 (10/13/2022) | 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/2022) | Dimension Reduction Johnson Lindenstrauss Transofrm | Chapter 2 of Foundations of DS Impossiblity of Dimension Reduction in L1 | ||
| Lecture 9 (10/27/2022) | Schwartz-Zippel Lemma | Algebraic Algorithms for Matchings | ||
| Lecture 10 (11/01/2022) | Linear Algebra Background: SVD, Det, Trace | |||
| Lecture 11 (11/03/2022) | 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/2022) | 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/2022) | Spectral Graph Theory, Clustering | |||
| Lecture 14 (11/17/2022) | ||||
| Lecture 15 (11/22/2022) | Power Method | PCA Graph Drawing | ||
| (11/24/2021) | No class: Thanks Giving | |||
| Lecture 16 (11/29/2022) | Linear Programming and the Ellipsoid Method | |||
| 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 | ||