We will study the design and analysis of algorithms from a modern perspective with a particular focus on techniques that find use in many subfield 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: Fri 2:50-3:35 in CSE 636.
Lectures: Monday - Fri 1:30 - 2:50 at EE 037
Teaching Assistants: Dorna Abdolazimi, Kuikui Liu
Office hours: Tuesday 12:30-1:30 (Dorna), Wednesday 3:00-4:00 (Kuikui) at CSE1 220 .
Discussion Board
Assignments
- Assignment-1, due Friday October 11th, 6:00 PM Inputs: c1.in, c2.in, c3.in
- Assignment-2, due Oct 27th, 6:00 PM, Inputs: lsh-1.in, lsh-2.in, lsh-3.in
- Assignment-3, due Nov 10th, 6:00 PM
- Assignment-4, due Nov 25th, 6:00 PM
- Assignment-5, due Dec 6th, 6:00 PM
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
- 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
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/27/2019) | Introduction, Contraction Algorithm | MR Section 1.1 Minimum cuts in Near Linear time | ||
| Lecture 2 (09/30/2019) | Concentration Bounds | MR Sections 3.1,3.2.,3.3 | ||
| Lecture 3 (10/04/2019) | Strong Concentration Bounds | MR Sections 4.1,4.2 | ||
| Lecture 4 (10/7/2019) | Hashing | Pairwise Independence and Derandomization | ||
| Lecture 5 (10/11/2019) | Streaming | Chapter 1 of Roughgarden's Course AMS paper | ||
| Lecture 6 (10/14/2019) | Locally Sensitive Hash Functions | A survey by Bernard Chazelle Indyk-Motwani paper Data Dependent hashing for NNS | ||
| Lecture 7 (10/18/2019) | Curse of Dimensionality, Dimension Reduction | Chapter 2 of Foundations of DS Impossiblity of Dimension Reduction in L1 | ||
| Lecture 8 (10/21/2019) | Curse of Dimensionality Continued | |||
| Lecture 9 (10/25/2019) | Schwartz-Zippel Lemma | Derandomized PIT implies Amazing Results Harvey's algebraic algorithm Bipartite matching is in quasi-NC General matching is in quasi-NC | ||
| Lecture 10 (10/28/2019) | Linear Algebra Background: SVD, Det, Trace | |||
| Lecture 11 (11/01/2019) | Low Rank Approximation | Sections 3.1-3.4 of DS Chapter 4 of Sketching Book Paper 1, Paper 2 on fast Low rank approximation A theoretical result on nonnegative matrix factorization | compressimage.m einstein.jpg | |
| Lecture 13 (11/08/2019) | Spectral Graph Theory | Low Rank Approx for Maxcut on Sprase Graphs Planted Partitioning using Low Rank Approx Goemans and Williamson's Approx Alg for Maxcut Different Objective fns for Clustering Approx Maxcut on Expander Graphs | ||
| (11/11/2019) | No Class: Veterans Day | |||
| Lecture 14 (11/15/2019) | Cheegers Inequlity, Spectral Clustering |
See here for proof of Hard Dir of Cheeger Local Graph Clustering Algorithms Higher Order Cheeger Inequalities Spectral Clustering |
||
| Lecture 15 (11/18/2019) | Spectral Sparsification |
Random graphs are almost Ramanujan | graph-drawing.tar imseg.tar | |
| Lecture 16 (11/22/2019) | Linear Modeling |
Goemans Lecture notes on Ellipsoid algorithm Faster Algorithms for solving LPs | ||
| Lecture 17 (11/25/2019) | MDPs, LP Rounding | Boyd's course on Convex Optimization | ||
| (11/29/2019) | No Class: Thanks Giving Day | |||
| Lecture 18 (12/02/2019) | LP Rounding, Duality | Applications" of LP in Randomized Rounding | ||
| Lecture 19 (12/06/2019) | Duality, Submodular Maximization | |||
