Instructor: Kamesh Munagala
Fall Semester, 2010
This course will cover algorithm design techniques at a graduate level. Topics include graph algorithms, shortest paths, amortization and search trees, randomization, hashing, fingerprinting, divide and conquer applied to FFT and matrix multiplication, network flows, matchings, stable marriage, linear programming, simplex algorithm, zerosum gamnes, duality, and NPCompleteness.
CPS130 or equivalent as a hard prerequisite. If you have never studied algorithms before, please read up on greedy algorithms and dynamic programming, or take CPS130 instead of this course.
Assignments and grades are posted via blackboard
There are two tracks for this course  Theory Track and Project Track. The project is here. You have to let me know which track you are choosing by October 19.
Slides that explain the material from the KleinbergTardos book can be found here
Administration:
Lectures: Tue/Thu 1:152:30 (D106 LSRC)
Office Hours: (Kamesh) Wed 45pm (D205 LSRC)
(Sudhanshu) Mon 24pm (D229 LSRC)
Grading:
Theory Track: Homeworks (30%), MidTerm (30%), Final (40%).
Project Track: Homeworks (15%), MidTerm (15%), Project (30%), Final (40%).
The Project Track students will be required to submit solutions to only 2 questions per homework. You have to let me know which track you are choosing by October 19.
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.
Additional Reading:
(Lec 2) Buckets, heaps, lists, and monotone priority queues
(Lec 2) Fibonacci Heaps used to implement Dijkstra's and Prim's algorithms in O(m + n log n) time
(Lec 7) The BurrowsWheeler Transform (aka bzip on UNIX): Clever Compression using MTF
(Lec 11) Skip Graphs  Peertopeer routing using skip lists
(Lec 14) Survey article on network applications of Bloom filters
(Lec 14) Consistent Hashing  One of the key ideas behind Akamai Technologies
(Lec 14) Distributed hash tables  Efficient data management in P2P networks
(Lec 14) Codedivision Multiple Access (CDMA) uses "hashing" for wireless communication.
(Lec 20) Packet switching: Great application of fast table lookups, permutation networks & matchings
(Lec 20) Stable marriages
Lect. 
Date 
Topics 
Reading List 
1 
Aug. 31 
Graph Algorithms: Breadth First Search, Topological Sort, Strongly connected components, Testing bipartiteness 
KT, Chapter 3 CLRS, Chapter 22 DPV, Chapter 3,4 
2 
Sep. 2 
Greedy Algorithms: Shortest paths: Dijkstra's Algorithm Implementation via priority queues 
KT, Chapter 4 CLRS, Chapter 23, 24 DPV, Chapter 5 
3 
Sep. 7 
Spanning trees, Cut and cycle properties Kruskal's and Prim's Algorithms 
KT, Chapter 4 DPV, Chapter 5 
4 
Sep. 9 
Data Structures: Unionfind implementations Amortization, Binary counting 
Notes (by Edelsbrunner) CLRS, Chapter 21 
5 
Sep. 14 
Analysis of unionfind with path compression 
DPV, Chapter 5 
6 
Sep. 16 
Search Trees: 24 Trees, Amortized analysis of reorder Lossless Data Compression: Huffman Encoding 
Notes (by Edelsbrunner) DPV, Chapter 5 
7 
Sep. 21 
Kraft's inequality, Optimal codelength and Entropy MovetoFront Coding and Competitive analysis 

8 
Sep. 23 
Dynamic Programming: Memoization, Weighted Interval Seheduling, Integer Knapsack 
KT, Chapter 6, DPV, Chapter 6 
9 
Sep. 28 
Shortest path algorithms: Bellman's equations, BellmanFord algorithm Matrix multiplication, FloydWarshall algorithms 
KT, Chapter 6.8, 6.9 CLRS, Chapter 24, 25 DPV, Chapter 6 
10 
Sep. 30 
Spaceefficient Dynamic Programming: FloydWarshall, SmithWaterman algorithms Hirschberg's implementation via Recursion 
KT, Chapter 6.6, 6.7 
11 
Oct. 5 
Randomization: Linearity of Expectation Random Search Trees, Quicksort 
KT, Chapter 13 CLRS, Chapter 5,7 
12 
Oct. 7 
MIDTERM (Lec. 110) 



FALL BREAK 

13 
Oct. 14 
Skip Lists Perfect Hashing 
CLRS, Chapter 11 
14 
Oct. 19 
Universal Hashing Bloom Filters 
KT, Chapter 13.6 Lecture Notes (Milterson) 
15 
Oct. 21 
RabinKarp Fingerprinting Divide and Conquer: Recurrence Relations, Counting inversions, Closest pair of points 
KT, Chapter 5.5 CLRS, Chapter 28 DPV, Chapter 2 
16 
Oct. 26 
Polynomial multiplication by evaluations Introduction to the Fourier Transform The Fast Fourier Transform Algorithm 
CLRS, Chapter 30 KT, Chapter 5.6 DPV, Chapter 2 
17 
Oct. 28 
FFT and Signal Processing, Permutation networks Network Flows: The MaxFlow and MinCut Problems The FordFulkerson Augmentation Algorithm 
CLRS, Chapter 26 KT, Chapter 7 DPV, Chapter 7 
18 
Nov. 2 
The Maxflow Mincut Theorem Capacity scaling and EdmondsKarp Algorithms 
KT, Chapter 7 
19 
Nov. 4 
Applications of MaxFlow and MinCut: Bipartite Matchings and Hall's Theorem, Disjoint Paths and Menger's Theorem 
CLRS, Chapter 26 KT, Chapter 7 
20 
Nov. 9 
Circulations with Demands, Project Scheduling, Image Segmentation 
KT, Chapter 7 
21 
Nov. 11 
Linear Programming: Expressing Problems as LPs The Dual Program Weak and Strong LP Duality 
CLRS, Chapter 29 Notes (CMU) 
22 
Nov. 16 
The Simplex Algorithm Applications of Linear Programming and Duality Shortest paths and network flows revisited 
CLRS, Chapter 29 DPV, Chapter 7 Notes (M. X. Goemans) 
23 
Nov. 18 
Flows with costs, Zero Sum Games NPCompleteness: Easy and hard problems CookLevin Theorem, Polytime Reductions 
CLRS, Chapter 34 KT, Chapter 8,9 DPV, Chapter 7,8 
24 
Nov. 23 
NPCompleteness Proofs: TSP, Subset Sum, Independent Set, Vertex Cover 
KT, Chapter 8,9 DPV, Chapter 8 


THANKSGIVING 

25 
Nov. 30 
Coping with NPCompleteness: Approximation Algorithms: Knapsack, Vertex Cover Connection to Linear Programming 
KT, Chapter 11 
26 
Dec. 2 
Efficient algorithms for special graphs Fixed parameter tractability 
KT, Chapter 10 

Dec. 18 
FINAL EXAM (710 PM) 
