Instructor: Kamesh Munagala
Fall Semester, 2011
This course will cover algorithm design techniques at a
graduate level. Topics include network flows, linear programming, NPCompleteness, approximation algorthms, randomization, and online algorithms.
CPS130 or equivalent is a HARD prerequisite. If you have never studied algorithms before, you have to take CPS130 instead of this course.
Discussions will be conducted via Piazza. Please post questions/doubts/comments there, and answer questions posted by your classmates.
Assignments and grades are posted via Blackboard.
Administration:
Lectures: Mon/Wed 1:152:30 (D106 LSRC)
Office Hours: (Kamesh) Tue 24pm (D205 LSRC)
(Will)
Thu 24pm (D104 LSRC)
Grading: Homeworks (40%), MidTerm (30%), Take home final (30%).
Quals Requirement: To pass the algorithm qualifier requirement, you need a grade of B+ or higher in the course.
Course Textbooks:
[KT] Algorithm Design by Jon Kleinberg and Eva Tardos. (required)
[CLRS] Introduction to Algorithms by T. Cormen, C. Leiserson, R. Rivest, and C. Stein. (optional)
[DPV] Algorithms by S. Dasgupta, C. Papadimitriou, and U. Vazirani. (optional)
Slides from the [KT] book, and a preprint of the [DPV] book are available online.
Course notes from CS261 at Stanford (courtsey Serge Plotkin).
Lect. 
Date 
Topics 
Reading List 
1 
Aug. 29 
Shortest Paths: Breadth first search, Dijkstra's Algorithm, Dynamic Programming 
KT, Chapter 4, 6.8, 6.9 CLRS, Chapter 23, 24, 25 
2 
Aug. 31 
Network Flows: The MaxFlow and MinCut Problems The FordFulkerson Augmentation Algorithm The Maxflow Mincut Theorem 
CLRS, Chapter 26 DPV, Chapter 7 
3 
Sep. 5 
Capacity scaling and EdmondsKarp Algorithms 
KT, Chapter 7 
4 
Sep. 7 
Applications of MaxFlow and MinCut: Hall's Theorem, Menger's Theorem, Circulations, Project Scheduling, Image Segmentation 
CLRS, Chapter 26 
5 
Sep. 12 
Linear Programming: Expressing Problems as LPs Simplex Algorithm 
CLRS, Chapter 29 
6 
Sep. 14 
Linear Programming Duality: Taking the dual 
Notes (M. X. Goemans) 
7 
Sep. 19 
Farkas' lemma, Proof of strong duality 
Notes (M. X. Goemans) 
8 
Sep. 21 
Applications of Linear Programming and Duality: Shortest paths, Mincut, Bipartite matchings via LPs 

9 
Sep. 26 
Flows with costs, Zerosum games via linear programming  
10 
Sep. 28 
NPCompleteness: Easy and hard problems CookLevin Theorem, Polytime Reductions 
CLRS, Chapter 34 DPV, Chapter 8 
11 
Oct. 3 
Approximation algorithms: Metric TSP, Knapsack 
KT, Chapter 11 
12 
Oct. 5 
MIDTERM (Lec. 110) 



FALL BREAK 

13 
Oct. 12 
Greedy algorithms: Minimum makespan, Kcenter 
KT, Chapter 11 
14 
Oct. 17 
Set cover, Disjoint paths  KT, Chapter 11 
15 
Oct. 19 
Vertex cover via LP duality  KT, Chapter 11 
16 
Oct. 24 
Local Search: Mindegree spanning trees 
KT, Chapter 12 Lecture Notes 
17 
Oct. 26 
Randomized Algorithms: Linearity of expectation, Algorithms for MAXkSAT 
KT, Chapter 13 
18 
Oct. 28 
Global mincuts Universal Hashing 
Lecture Notes (Milterson) KT, Chapter 13 
19 
Nov. 2 
Bloom Filters RabinKarp Fingerprinting 

20 
Nov. 7 
Tail inequalities and applications to packet routing 
KT, Chapter 13 
21 
Nov. 9 
Online algorithms and Competitive Analysis: Ski rental, List update 
KT, Chapter 13 
22 
Nov. 14 
Data compression: Kraft's inequality, Optimal codelength and Entropy Analysis of MovetoFront Coding 

23 
Nov. 16 
Deterministic algorithms for paging 

24 
Nov. 21 
Randomized paging  KT, Chapter 13 


THANKSGIVING 

25 
Nov. 28 
Weighted majority algorithm 

26 
Nov. 30 
<slack> TAKE HOME FINAL 

Additional Reading:
(Lec 1) Buckets, heaps, lists, and monotone priority queues
(Lec 1) Fibonacci Heaps used to implement Dijkstra's and Prim's algorithms in O(m + n log n) time
(Lec 4) Packet switching: Great application of fast table lookups, permutation networks & matchings
(Lec 4) Stable marriages
(Lec 22) The BurrowsWheeler Transform (aka bzip on UNIX): Clever Compression using MTF
(Lec 18) Skip Graphs  Peertopeer routing using skip lists
(Lec 19) Survey article on network applications of Bloom filters
(Lec 19) Consistent Hashing  One of the key ideas behind Akamai Technologies
(Lec 19) Distributed hash tables  Efficient data management in P2P networks
(Lec 19) Codedivision Multiple Access (CDMA) uses "hashing" for wireless communication.