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, Allen Center 636
Lectures: Tue - Thu 10:00 - 11:20 in Allen Center 305
Teaching Assistants:
- Farzam Ebrahimnejad, Office hour: Wednesdays 3:00-3:50 at CSE2 153.
- Daogao Liu, Office hour: Mondays 4:00-4:50 at CSE1 220.
Discussion Board
Assignments
- Assignment-1, due Sunday October 09th, 11:59 PM
- Assignment-2, due Sunday October 16th, 11:59 PM
- Assignment-3, due Monday October 23rd, 11:59 PM
- Assignment-4, due Monday October 30th, 11:59 PM, Input file for HW4-P1: p4.in
- Assignment-5, due Tuesday Nov 7th, 11:59 PM
- Assignment-6, due Tuesday Nov 14th, 11:59 PM
- Assignment-7, due Tuesday Nov 27th, 11:59 PM
- Assignment-8, due Tuesday Dec 6th, 11:59 PM
Class Mailing list: cse521a_au23
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
- Spectral Expanding Expanders
- Authoritative Sources in a Hyperlinked Environment
- An Improved Distributed Algorithm for Maximal Independent Set
- Finding Maximum Flow using Electrical Flows
- Outcome Indistinguishability
- Parallel Graph Connectivity in Log Diameter Rounds
- Negative-Weight Single-Source Shortest Paths in Near-linear Time
- Approximately Coloring 3-colorable graphs
- 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/28/2023) | Introduction, Contraction Algorithm | video | MR Section 1.1 | ||
| Lecture 2 (10/03/2023) | Concentration Bounds | video | MR sections 3.1, 3.2, 3.3 | ||
| Lecture 3 (10/05/2023) | Strong Concentration Bounds | video | MR sections 4.1, 4.2. | ||
| Lecture 4 (10/10/2023) | Hashing | video | Pairwise Independence and Derandomization | ||
| Lecture 5 (10/12/2023) | Unbiased Estimators | video | |||
| Lecture 6 (10/17/2023) | Streaming / Locally Sensitive Hash Functions | vidoe | 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/24/2023) | Dimension Reduction Johnson Lindenstrauss Transform | video-1, video-2 | Chapter 2 of Foundations of DS Impossiblity of Dimension Reduction in L1 | ||
| Lecture 9 (10/26/2023) | Schwartz-Zippel Lemma | video | Algebraic Algorithms for Matchings | ||
| Lecture 10 (10/31/2023) | Linear Algebra Background: SVD, Det, Trace | video | |||
| Lecture 11 (11/02/2023) | Low Rank Approximation | video | Sections 3.1-3.4 of DS Chapter 4 of Sketching Book Paper 1, Paper 2 on fast low rank approximation | ||
| Lecture 12 (11/07/2023) | Max Cut Problem | video | Low rank approx for Maxcut on Sparse Graphs Planted Partitioning using Low rank Approximation Goemans and Williamson Approximation Algorithm for Maxcut | ||
| Lecture 13 (11/09/2023) | Spectral Graph Theory, Clustering | video | |||
| Lecture 14 (11/14/2023) | video | ||||
| Lecture 15 (11/16/2023) | Power Method | video | PCA Graph Drawing | ||
| (11/21/2023) | NO class: Thanks giving week | ||||
| (11/23/2021) | No class: Thanks Giving | ||||
| Lecture 16 (11/28/2023) | Linear Programming and the Ellipsoid Method | video | |||
| Lecture 17 (11/30/2023) | LP and SDP Rounding | video | |||
| Lecture 18 (12/05/2023) | Duality | video | |||
| Lecture 19 (12/07/2023) | Submodular Maximization | video-1 video-2 | Influence Maximization Problem | ||