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: Wed 2:50-3:35, zoom link.
Lectures: Monday - Wed 1:30 - 2:50, zoom link.
Teaching Assistants: Farzam Ebrahiminejad, Kuikui Liu
Office hours: Tuesday 3:00-3:50 (Farzam) zoom link, Thursday 1:30-2:20 (Kuikui) zoom link.
Discussion Board
Assignments
- Assignment-1, due Friday October 16th, 11:59 PM Inputs for P1: mcut-1.in, mcut-2.in, mcut-3.in, mcut-4.in
- Assignment-2, due Nov 1st, 11:59 PM,
- Assignment-3, due Nov 19th, 11:59 PM, psdnorm.in
- Assignment-4, due Dec 8th, 11:59 PM
Class Mailing list: cse521a_au20
Final Project
Here are some notes about the final project. Suggestions- Finding Frequent Items in Data Streams
- 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
- Higher Order Cheeger Inequalities and Spectral Clustering
- Graph Clustering using Random Walks
- Approximation Algorithms for Hierarchical Clustering
- Linear size Spectral Sparsifiers
- A Markov Chain Alg for Sampling DPPs
- 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
Common Knowledge
Related Materials
Similar courses at other schools- Advanced Algorithms by Sanjeev Arora
- Graduate Algorithms by Lap Chi Lau
- Combinatorial Algorithms and Data Structures by Satish Rao and Umesh Vazirani
- 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
| Lecture | Topic | Notes | Reading | Files | |
|---|---|---|---|---|---|
| Lecture 1 (09/30/2020) | Introduction, Contraction Algorithm | pdf notes | MR Section 1.1 Minimum cuts in Near Linear time | ||
| Lecture 2 (10/05/2020) | Concentration Bounds | pdf Notes | MR sections 3.1, 3.2, 3.3 | ||
| Lecture 3 (10/07/2020) | Strong Concentration Bounds | pdf notes | MR sections 4.1, 4.2. | ||
| Lecture 4 (10/12/2020) | Hashing | pdf Notes | Pairwise Independence and Derandomization | ||
| Lecture 5 (10/14/2020) | Unbiased Estimators | pdf notes | |||
| Lecture 6 (10/19/2020) | Streaming / Locally Sensitive Hash Functions | pdf Notes | Chapter 1 of Roughgarden's Course AMS paper | ||
| Lecture 7 (10/21/2020) | LSH, Curse of Dimensionality | pdf Notes | A Survey by Bernard Chazelle Indyk-Motwani Paper Data Dependent hashing for NNS | ||
| Lecture 8 (10/26/2020) | Notes | Chapter 2 of Foundations of DS Impossiblity of Dimension Reduction in L1 | |||
| Lecture 9 (10/28/2020) | Schwartz-Zippel Lemma | pdf notes | Derandomized PIT implies amazing results Bipartite matching is in quasi-NC General matching is in quasi-NC | ||
| Lecture 10 (11/02/2020) | Linear Algebra Background: SVD, Det, Trace | pdf Notes | |||
| Lecture 11 (11/04/2020) | Low Rank Approximation | pdf Notes | Sections 3.1-3.4 of DS Chapter 4 of Sketching Book Paper 1, Paper 2 on fast low rank approximation | ||
| Lecture 12 (11/09/2020) | Max Cut Problem | pdf Notes | Low rank approx for Maxcut on Sparse Graphs Planted Partitioning using Low rank Approximation Goemans and Williamson Approximation Algorithm for Maxcut | compressimg.m, einstein.jpg | |
| (11/11/2020) | No Class: Veterans Day | ||||
| Lecture 13 (11/16/2020) | Spectral Graph Theory, Clustering | pdf Notes-13 Notes-14 | |||
| Lecture 14 (11/18/2020) | |||||
| Lecture 15 (11/23/2020) | Cheeger's Inequality, Spectral Clustering | pdf Notes | draw.m, grid.m, carbon.m | ||
| (11/25/2020) | No class | ||||
| Lecture 16 (11/30/2020) | Linear Modeling | pdf Notes | |||
| Lecture 17 (12/02/2020) | MDPs | pdf Notes | |||
| Lecture 18 (12/07/2020) | Duality, LP Rounding | pdf Notes | |||
| Lecture 19 (12/09/2020) | Spectral Sparsification, LP Rounding | pdf Notes | |||
