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: Mon, Wed 3:00-3:45 in CSE 636.
Lectures: Monday - Wednesday 1:30 - 2:50 at JHN 022
Teaching Assistant: Farzam Ebrahiminejad
Office hours: Tuesday/Friday 15:00-15:45, CSE 220.
Discussion Board
Assignments
- Assignment-1, due Monday October 15th, 12:00 PM Inputs: b0.in, b1.in, b2.in, b3.in
- Assignment-2, due Oct 29th, Inputs: j0.in, j1.in, j2.in, j3.in, j4.in jacc.cpp
- Assignment-3, due Nov 12th.
- Assignment-4, due Dec 5th.
Final Project
Here are some notes about the final project. Suggestions- Finding Frequent Items in Data Streams
- Beating CountSketch for Heavy Hitters
- Bipartite Matching is in Quasi NC
- Low Rank Approximation for PSD
- A Combinatorial Algorithm for SDD Linear Systems
- Solving Laplacian Linear Systems by Approximate Gaussian Elimination
- Graph Clustering using Random Walks
- Approximation Algorithms for Hierarchical Clustering
- Linear size Spectral Sparsifiers
- Space Efficient Algorithms for Subset Sum
- A Markov Chain Alg for Sampling DPPs
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 |
|---|---|---|---|---|
| (09/26/2018) | No Class: Conference | |||
| Lecture 1 (10/01/2018) | Introduction, Contraction Algorithm | MR Section 1.1 Minimum cuts in Near Linear time | ||
| Lecture 2 (10/03/2018) | Concentration Bounds | MR Sections 3.1,3.2.,3.3 | ||
| Lecture 3 (10/08/2018) | Strong Concentration Bounds | MR Sections 4.1,4.2 | ||
| Lecture 4 (10/10/2018) | Hashing | |||
| Lecture 5 (10/15/2018) | Streaming | Chapter 1 of Roughgarden's Course AMS paper | ||
| Lecture 6 (10/17/2018) | Locally Sensitive Hash Functions | A survey by Bernard Chazelle Indyk-Motwani paper Data Dependent hashing for NNS | ||
| Lecture 7 (10/22/2018) | Curse of Dimensionality, Dimension Reduction | Chapter 2 of Foundations of DS Impossiblity of Dimension Reduction in L1 | ||
| Lecture 8 (10/24/2018) | 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 9 (10/31/2018) | Linear Algebra Background: SVD, Det, Trace | |||
| Lecture 11 (11/05/2018) | 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 12 (11/07/2018) | Max Cut, 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 | ||
| (11/12/2018) | No Class: Veterans Day | |||
| Lecture 13 (11/14/2018) | Spectral Graph Theory, Clustering |
Local Graph Clustering Algorithms Different Objective fns for Clustering | graph-drawing.tar spectral-clusterin.tar | |
| Lecture 14 (11/19/2018) | Spectral Clustering |
Spectral Clustering Approx Maxcut on Expander Graphs Higher Order Cheeger Inequalities See here for proof of Hard Dir of Cheeger | ||
| Lecture 15 (11/21/2018) | Power Method, Spectral Sparsification | Spectral Sparsification by Effective Resistance Linear sized Spectral Sparsifiers Vertex Sparsifiers My notes on effective resistance | ||
| Lecture 16 (11/26/2018) | Linear Modeling | Random graphs are almost Ramanujan Boyd's course on Convex Optimization Goemans Lecture notes on Ellipsoid algorithm Faster Algorithms for solving LPs | ||
| Lecture 17 (11/28/2018) | MDPs, Rounding | Applications" of LP in Randomized Rounding | ||
| Lecture 18 (12/03/2018) | LP Rounding, Duality | |||
| Lecture 19 (12/05/2018) | Max-Flow, Min Cut | |||
