Instructor: Kamesh Munagala
Fall Semester, 2011
This course will cover algorithm design techniques at a
graduate level. Topics include network flows, linear programming, NP-Completeness, 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:15-2:30 (D106 LSRC)
Office Hours: (Kamesh) Tue 2-4pm (D205 LSRC)
(Will)
Thu 2-4pm (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 pre-print 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 Max-Flow and Min-Cut Problems The Ford-Fulkerson Augmentation Algorithm The Max-flow Min-cut Theorem |
CLRS, Chapter 26 DPV, Chapter 7 |
|
3 |
Sep. 5 |
Capacity scaling and Edmonds-Karp Algorithms |
KT, Chapter 7 |
|
4 |
Sep. 7 |
Applications of Max-Flow and Min-Cut: 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, Min-cut, Bipartite matchings via LPs |
|
| 9 |
Sep. 26 |
Flows with costs, Zero-sum games via linear programming | |
| 10 |
Sep. 28 |
NP-Completeness: Easy and hard problems Cook-Levin Theorem, Poly-time Reductions |
CLRS, Chapter 34 DPV, Chapter 8 |
| 11 |
Oct. 3 |
Approximation algorithms: Metric TSP, Knapsack |
KT, Chapter 11 |
|
12 |
Oct. 5 |
MIDTERM (Lec. 1-10) |
|
|
|
|
FALL BREAK |
|
|
13 |
Oct. 12 |
Greedy algorithms: Minimum makespan, K-center |
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: Min-degree spanning trees |
KT, Chapter 12 Lecture Notes |
|
17 |
Oct. 26 |
Randomized Algorithms: Linearity of expectation, Algorithms for MAX-k-SAT |
KT, Chapter 13 |
|
18 |
Oct. 28 |
Global min-cuts Universal Hashing |
Lecture Notes (Milterson) KT, Chapter 13 |
|
19 |
Nov. 2 |
Bloom Filters Rabin-Karp 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 code-length and Entropy Analysis of Move-to-Front 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 Burrows-Wheeler Transform (aka bzip on UNIX): Clever Compression using MTF
(Lec 18) Skip Graphs -- Peer-to-peer 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) Code-division Multiple Access (CDMA) uses "hashing" for wireless communication.