CS 7800: Advanced Algorithms

Fall 2010

Tentative Calendar
 Week  Topic Problem Sets

Sep 6 Administrivia; Algorithms & their complexity
The Selection problem: Randomized linear-time algorithm 

POW-1 9.1-9.2
Sep 13
Deterministic divide-and-conquer algorithm for selection
Strassen's algorithm for matrix multiplication
Introduction to graphs & graph algorithms;
MST: Structural properties; Kruskal's algorithm;  
PS1 out
POW-2,3 9.3, 4.2, 22.1-22.3, 23
Sep 20
MST: Prim's and Borouvka's algorithms; Priority queues
Randomized linear-time algorithm of Karger-Klein-Tarjan
MST verification and least common ancestor calculations
1 due; 2 out
23, 6.1-6.3, 6.5
King, Eisner, Hagerup
Bender, Farach-Colton
Sep 27
Greedy algorithms: Huffman encoding
Matriods and greedy methods
Dynamic programming: Longest Common Subsequence; Application to shortest paths
PS2 out
POW 4-5
16.1-4, 15.3-15.4
24.1, 25.1
Oct 4
Single-source and all-pairs shortest paths
Network flows: Maxflow-mincut theorem
2 due; 3 out

24.3, 25.2, 26.1
Oct 11
No class on Monday, Columbus Day
Network Flows: Ford-Fulkerson and Edmonds-Karp algorithms
PS3 out

Oct 18
Network Flows, contd
Linear programming
Formulating problems as linear programs

Notes on LP
29.1-29.2, 29.4
Oct 25 Linear programming: Geometry and Duality
Linear programming: The simplex algorithm
3 due; PS4 out
POW 6-7
29.3, 11
Nov 1
Complete Simplex and Farkas Lemma
NP-completeness: P, NP, polynomial-time reductions

Farkas Lemma Proof
Nov 8
Approximation Algorithms
Set cover, randomization and linear programming
4 due
Midterm out
Approx Algs
Nov 15 Random walk algorithm for undirected connectivity
Markov chains
Midterm due POW 8-10

Nov 22
Fast Fourier Transform
No class on Thanksgiving Eve Nov 24
PS5 out

Nov 29
Splay Trees
Games and Solution Concepts

POW 11-14
Sleator's notes
Dec 6
Nash equilibria, Zero-sum games
Market algorithms
Mechanism design
5 due
AGT book, chapters 1,9
Dec 15
Final Exam, due Dec 16

The reading assignments list sections and chapters of the third edition of the textbook.

Note: All handouts are in PDF.