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 EEB 031
Teaching Assistant: Robbie Weber
Office hours: Tue at 11:00, Thu at 2:00 in CSE 220.
Each student must scribe one lecture. Here is the scribe template file.
Discussion Board
Assignments
Assignments will be submitted via Canvas.- Problem Set 1 (Latex) due date January 18th at 12:00 PM. Input files for Problem 2: a0.in, a1.in, a2.in
- Problem Set 2 (Latex) due date Jan 30th at 12:00 PM. Input file for Problem 2: oregon2_010331.txt
- Midterm (Latex) due date Feb 10 at 12:00 PM. Input file for Problem 5: lsh.in
- Problem Set 4 (Latex due date Feb 26th at 12:00 PM. Solution to Problem 4.
- Problem Set 5 due date Mar 09th at 12:00 PM. solution
Notes about the final project
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
- 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
| Lecture | Topic | Notes | Reading | Files |
|---|---|---|---|---|
| Lecture 1 (01/04/17) | Introduction, Contraction Algorithm | MR section 1.1 | ||
| Lecture 2 (01/09/17) | Sampling, Concentration Bounds | A list of concentration inequalities | ||
| Lecture 3 (01/11/17) | Concentration Bounds, Hash Functions | |||
| (01/16/17) | No class: Martin Luther King Day | |||
| Lecture 4 (01/18/17) | Hashing | The two tier hashing Algorithm paper Notes by Jeff Erickson Notes by Sanjeev Arora Summer School on Hashing | ||
| Lecture 5 (01/23/17) | Streaming | [AMS] paper Chapter of 1 of Roughgarden's course | ||
| Lecture 6 (01/25/17) | Locally Sensitive Hashing | A survey by Bernard Chazelle Indyk-Motwani's Paper Charikar's Paper Data Dependent Hashing for NNS | ||
| Lecture 7 (01/30/17) | Shwartz-Zippel Lemma, Perfect Matching | Derandomized Polynomial Identity testing implies Amazing result in Complexity Theory Harvey's algebraic algorithm Bipartite matching is in quasi-NC | ||
| Lecture 8 (02/01/17) | Linear Algebra Background, Low Rank Approximation | see Trevisan's lecture note for background on spectral theorem | ||
| (02/06/17) | No class: Due to Snow | |||
| Lecture 9 (02/08/17) | Max cut, Spectral Graph Theory | Sections 3.1-3.4 of Hopcroft-Kannan Column subset selection Paper 1 Paper 2 on Low rank approximation in Almost linear time A markov chain algorithm for column subset selection A theoretical result on nonnegative matrix factorization | Matlab code Image | |
| Lecture 10 (02/13/17) | Max Cut, The Laplacian Matrix | Hopcroft-Kannan Chapter 5 of Kannan-Vempala Goemans and Williamson Approximation Algorithm for maxcut | ||
| Lecture 11 (02/15/17) | Spectral Partitioning, Cheeger's Inequality | Trevisan's spectral graph theory course Spielman's spectral graph theory course Higher order Cheeger inequalities k median and k center on planar graphs Trevisan's lecture notes on log(n) approximation for sparsest cut | ||
| (02/20/17) | No Class: Presidents Day | |||
| Lecture 12 (02/22/17) | Cheegers Inequality, Power Method | Spectral Clustering My lecture notes on Harder direction of Cheeger's inequality | ||
| Lecture 13 (02/27/17) | Power Method, Random Walks, |
See here and here for fast Laplacian solvers See here for applciatons of fast Laplacian solvers in Max-Flow | Graph Draw, Grid, carbon
A zip file of image segmentation files | |
| Lecture 14 (02/01/17) | Random Walks, Linear Programming | An application of random walks in counting
See here and here for applications random walks in local graph clustering See here for fastest known algorithms for solving LPs | ||
| Lecture 15 (03/06/17) | LP Rounding, MDPs | Applications of LPs in Approximation Algorithms | ||
| Lecture 16 (03/08/17) | Duality and Applications | |||
