,

CPS532 Graduate Algorithms

Instructor: Kamesh Munagala

    Tue/Thu 3:05 - 4:20 @ A247 LSRC

Fall 2017


Course Outline: This course will cover algorithm design techniques at a graduate level. Topics include the mainstays of modern algorithmic thinking: mathematical programming, approximation algorithms, hashing, and algebraic methods.

CPS330 or equivalent is a hard prerequisite. THIS COURSE IS NOT AN INTRODUCTION TO ALGORITHMS!!!
If you have never studied algorithms before, you have to take CPS330 or CPS531 instead.

Office Hours:
Kamesh Munagala:         Mon 9:45 - 10:30am,  LSRC D205
Abhinandan Nath (TA):  Thu 4:30 - 5:30pm,   LSRC D214
Grading:  Five homeworks (40%),  Three in-class mid-term exams (20% each).

I will choose the best 5 out of 6 homeworks for computing the grade.
Reading Material:  I will mainly use material from these sources. Buying the books is optional. I have put pointers to easy-to-digest notes.

[KT]      Algorithm Design  by Jon Kleinberg and Eva Tardos.   
[CLRS]  Introduction to Algorithms by T. Cormen, C. Leiserson, R. Rivest, and C. Stein.  
[DPV]   Algorithms by S. Dasgupta, C. Papadimitriou, and U. Vazirani. 

Slides from the [KT] book are available online.

Course notes from CS261 at Stanford (courtsey Serge Plotkin).

Lecture Schedule:

Lecture NumberDateTopicNotes
 Readings
Linear Programming
1
 Aug.  29
 Shortest Paths and Dynamic Programming [KT], Chapter 6
Slides
2
 Aug. 31
 Space efficient Dynamic Programming
3
 Sep. 5
 Maximum Flow Problem
Augmenting paths, Maxflow-mincut theorem
 [KT], Chapter 7
Slides
4
 Sep. 7
 Applications of max flow and min cut
Slides
5
 Sep. 12
 Linear Programming
Modeling problems as linear programs


[DPV], Chapter 7


Michel Goemans' Lecture notes
Plotkin's lecture notes
6
 Sep. 14
 Simplex Algorithm
7
 Sep. 19
 Duality
Complementary Slackness
8
 Sep. 21
9
 Sep. 26
 The Experts Problem
Notes, Chapter 8
10
 Sep. 28
 Multiplicative weight method
11
 Oct. 3
 Approximating multicommodity flows
 Notes, Chapter 9
 Plotkin's lecture notes
Approximation algorithms
12
 Oct. 5
 MIDTERM  1  (Lec. 1 - 8)

Oct. 10
 FALL BREAK
13
 Oct. 12
 Submodular maximization and greedy algorithms Notes, Chapter 3
14
 Oct. 17
 Random variables and large deviations

15
 Oct. 19
 Linear program lower bounds:
Randomized rounding and VLSI Layout
Primal-dual method and Vertex cover
 Lecture Notes
Plotkin's lecture notes
Slides
Hashing
16
Oct. 24
Universal Hashing
Miltersen's Notes
17
 Oct. 26
 Bloom filters Survey article
 Chapter 5.5.3 in [MU]
Count-min Sketch (Lecture notes)
18
 Oct. 31
 Similarity search
Nearest neighbor problem and K-d Trees
Lecture notes
 		Chapter 5.2 in this book
19
 Nov. 2
 The random projection method
Lecture notes Chapter 4 in [MU]
Lecture notes
Tutorial with simplest proof of JL Lemma
20
 Nov. 7
 Locality Sensitive Hashing
Estimators for Hamming, Jaccard, Cosine measures
 Lecture notes Paper1 Paper2
CACM Survey Article
21
 Nov. 9
 MIDTERM 2  (Lec. 13 - 21)

Algebraic Methods and Markov Chains
22
 Nov. 14
 Eigenvalues and Eigenvectors
 		Lecture notes
 Lecture notes
Lecture notes
23
 Nov. 16
 Principal Components Analysis (PCA)
 Lecture Notes
 Shalizi's chapter
Tomasi's notes
24
Nov. 21
Graph Laplacian
Spectral Partitioning 		Lecture Notes Tutorial
Lecture notes

 Nov. 23
 THANKSGIVING

25
Nov. 28
 Random walks: Markov Chains, Graph centralityLecture Notes Chapter 2 in Matt Jackson's book.
A simple description of PageRank
26
 Nov. 30
 Monte-Carlo Methods: DNF Counting, Metropolis


Dec. 5
 MIDTERM 3 (In Class; Lec. 16 - 26)