CSE 521: Design and Analysis of Algorithms (Spring 2016)

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.

Course evaluation: homework (~60%), final project (~40).
Discussion Board

Final Project

Due date: June 1st 23:59

You 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 Here is a list of related books
Tentative Schedule:
Lecture Topic Notes Reading Files
Lecture 1
Introduction, Contraction Algorithm Latex MR section 1.1
Lecture 2
Sampling, Concentration Bounds Latex A list of concentration inequalities
Lecture 3
Streaming, uniqueness, 2nd moment Latex [AMS] paper
Chapter of 1 of Roughgarden's course
Lecture 4
Hash Functions, Streaming Cont'd
Lecture 5
Schwartz-Zippel Lemma, Perfect Matchin Latex Harvey's algebraic algorithm
Lecture 6
Curse of Dimensionality, Dimesion Reduction Latex Chapter 2 of Hopcroft-Kannan
Fast Johnson Lindenstrauss
Impossibility of Dimension Reduction in l1
Lecture 7
Locally sensitive hashing, Nearest Neighbor Search Latex A survey by Bernard Chazelle
Indyk-Motwani's Paper
Charikar's Paper
Lecture 8
Linear Algebra Background:
Spectral Thm, SVD, Det, Trace
Latex See Trevisan's notes for more detailed proofs.
Lecture 9
PCA, Low rank approximation, Volume Sampling Latex Sections 3.1-3.4 of Hopcroft-Kannan Matlab Code, Image
Lecture 10
Low Rank Approximation in Optimization Latex Section 3.6.5 of Hopcroft-Kannan
Chapter 5 of Kannan-Vempala
Lecture 11
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
Lecture 12
Spectral Graph Theory, Cheeger's inequality Latex Section 4.2 of Kannan-Vempala
Hard direction of Cheeger's inequality
Spectral Clustering
Lecture 13
Power Method, Random Walks Latex Section 3.5 of Hopcroft-Kannan A tar file of Matlob codes for grpah drawing
Lecture 14
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
Linear Modeling, MDPs Latex A fast intro to Linear Programming by Thomas Ferguson
Chapter from algorithms textbook by DasGupta, Papadimitriou and Vazirani
Lecture 16
Duality Latex LPs: an algebraic view
Geometry of LPs
LP examples: max-flow, matching, vertex-cover
Lecture 17
Maximum Flow/Minimum cut Latex Applications of duality
Section 2.2 and 2.3 of Motwani-Raghavan book
Lecture 18
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
Submodular Functions Jan Vondrak's talk on submodular functions