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, zero-sum gamnes, duality, and NP-Completeness.
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 Kleinberg-Tardos book can be found here
Administration:
Lectures: Tue/Thu 1:15-2:30 (D106 LSRC)
Office Hours: (Kamesh) Wed 4-5pm (D205 LSRC)
(Sudhanshu) Mon 2-4pm (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 pre-print 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 Burrows-Wheeler Transform (aka bzip on UNIX): Clever Compression using MTF
(Lec 11) Skip Graphs -- Peer-to-peer 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) Code-division 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: Union-find implementations Amortization, Binary counting |
Notes (by Edelsbrunner) CLRS, Chapter 21 |
|
5 |
Sep. 14 |
Analysis of union-find with path compression |
DPV, Chapter 5 |
|
6 |
Sep. 16 |
Search Trees: 2-4 Trees, Amortized analysis of reorder Lossless Data Compression: Huffman Encoding |
Notes (by Edelsbrunner) DPV, Chapter 5 |
|
7 |
Sep. 21 |
Kraft's inequality, Optimal code-length and Entropy Move-to-Front 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, Bellman-Ford algorithm Matrix multiplication, Floyd-Warshall algorithms |
KT, Chapter 6.8, 6.9 CLRS, Chapter 24, 25 DPV, Chapter 6 |
|
10 |
Sep. 30 |
Space-efficient Dynamic Programming: Floyd-Warshall, Smith-Waterman 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. 1-10) |
|
|
|
|
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 |
Rabin-Karp 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 Max-Flow and Min-Cut Problems The Ford-Fulkerson Augmentation Algorithm |
CLRS, Chapter 26 KT, Chapter 7 DPV, Chapter 7 |
|
18 |
Nov. 2 |
The Max-flow Min-cut Theorem Capacity scaling and Edmonds-Karp Algorithms |
KT, Chapter 7 |
|
19 |
Nov. 4 |
Applications of Max-Flow and Min-Cut: 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 NP-Completeness: Easy and hard problems Cook-Levin Theorem, Poly-time Reductions |
CLRS, Chapter 34 KT, Chapter 8,9 DPV, Chapter 7,8 |
|
24 |
Nov. 23 |
NP-Completeness Proofs: TSP, Subset Sum, Independent Set, Vertex Cover |
KT, Chapter 8,9 DPV, Chapter 8 |
|
|
|
THANKSGIVING |
|
|
25 |
Nov. 30 |
Coping with NP-Completeness: 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 (7-10 PM) |
|