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, linear programming, dimensionality, clustering, sparsification, etc.
Administrative Information
Instructor: Shayan Oveis Gharan
Office Hours: By appointment, email me at shayan at cs dot washington dot edu.
Lectures: Monday - Wednesday 3:00 - 4:20 at EEB 045
Teaching Assistant: Alireza Rezaei
Office hours: Tue, Thu at 12:00-12:45 in CSE 218.
Discussion Board
Final Project
Due date: June 1st 23:59You are supposed to choose a theory paper (appeared in any of the theory conferences, FOCS, STOC, SODA, ICALP, APPROX, etc) and write a survey of it. The paper is supposed to be relatively recent, not earlier than 2000. You can make groups of at most 2 people working on the same project. You survey should contain the following items:
- Introduction: This part should contain the problem definition, motivations, applications, and the previous works.
- Main contributions: This part should contain the main results of the paper, the algorithm and the implications of the results. For example you are encouraged to give applications of the results related to your own fields of research.
- Overview of the proof: In this part you should give a high-level overview of the proof. What are the main ideas of the proof? What is the novelty of the paper which makes it different from the previous work.
- Details of the proof: In this part you should write your understanding of the proof. For example you can provide several examples for elaboration purposes. You can also try to go over the main steps and the main lemmas of the proof. Try to understand the proof as best as you can.
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 (03/28/16) | Introduction, Contraction Algorithm | Latex | MR section 1.1 | |
| Lecture 2 (03/30/16) | Sampling, Concentration Bounds | Latex | A list of concentration inequalities | |
| Lecture 3 (04/04/15) | Streaming, uniqueness, 2nd moment | Latex | [AMS] paper Chapter of 1 of Roughgarden's course | |
| Lecture 4 (04/06/15) | , Hash Functions, Streaming Cont'd |
Latex | ||
| Lecture 5 (04/11/15) | Schwartz-Zippel Lemma, Perfect Matchin | Latex | Harvey's algebraic algorithm | |
| Lecture 6 (04/13/15) | Curse of Dimensionality, Dimesion Reduction | Latex | Chapter 2 of Hopcroft-Kannan Fast Johnson Lindenstrauss Impossibility of Dimension Reduction in l1 | |
| Lecture 7 (04/018/15) | Locally sensitive hashing, Nearest Neighbor Search | Latex | A survey by Bernard Chazelle Indyk-Motwani's Paper Charikar's Paper | |
| Lecture 8 (04/20/15) | Linear Algebra Background: Spectral Thm, SVD, Det, Trace |
Latex | See Trevisan's notes for more detailed proofs. | |
| Lecture 9 (04/25/15) | PCA, Low rank approximation, Volume Sampling | Latex | Sections 3.1-3.4 of Hopcroft-Kannan | Matlab Code, Image |
| Lecture 10 (04/27/15) | Low Rank Approximation in Optimization | Latex | Section 3.6.5 of Hopcroft-Kannan Chapter 5 of Kannan-Vempala | |
| Lecture 11 (05/02/15) | Clustering, Spectral Partitioning | Latex | Conductance vs Other Clustering Measures Spectral partitioning in Planar graphs Spectral Partitioning and Image Segmentation | A tar file of all Matlab codes Image |
| Lecture 12 (05/04/15) | Spectral Graph Theory, Cheeger's inequality | Latex | Section 4.2 of Kannan-Vempala Hard direction of Cheeger's inequality Spectral Clustering | |
| Lecture 13 (05/09/15) | Power Method, Random Walks | Latex | Section 3.5 of Hopcroft-Kannan | A tar file of Matlob codes for grpah drawing |
| Lecture 14 (05/11/15) | Random Walks/Linear programming | Latex | Chapter 1 and 12 of Markov Chain, Mixing TIme Great intro to linear programming by Matousek and Gartner | |
| Lecture 15 (05/16/15) | Linear Modeling, MDPs | Latex | A fast intro to Linear Programming by Thomas Ferguson Chapter from algorithms textbook by DasGupta, Papadimitriou and Vazirani | |
| Lecture 16 (05/18/15) | Duality | Latex |
LPs: an algebraic view Geometry of LPs LP examples: max-flow, matching, vertex-cover Duality | |
| Lecture 17 (05/23/15) | Maximum Flow/Minimum cut | Latex | Applications of duality Section 2.2 and 2.3 of Motwani-Raghavan book | |
| Lecture 18 (05/25/15) | LP Rounding and Multipliative weight update | Chapters 4,5 of book by Williamson-Shmoys Chapters 1,2,3 of book by Lau, Ravi and Singh | ||
| (05/30/15) | NO CLASS: Memorial day | |||
| Lecture 19 (06/01/15) | Submodular Functions | Jan Vondrak's talk on submodular functions | ||
