CS G713: Advanced Algorithms

Fall 2003

Tentative Calendar

Week Topic Problem Sets
Handouts
Reading

Sep 10 Administrivia; Algorithms & their complexity; The Selection problem: Randomized linear-time algorithm 1 out Problem Set -1
POW-1
9, 22.1-22.3 (10, 23.1-23.3)

Sep 17
Deterministic algorithm for selection; Introduction to graphs & graph algorithms;
POW-2
POW-3
9, 22.1-22.3 (10, 23.1-23.3)

Sep 24
Minimum spanning trees: Structural properties; Prim's & Kruskal's algorithms; 1 due; 2 out POW-4
Problem Set -2
23 (24)

Oct 1 Data structures for disjoint sets: Union-find algorithms; Inverse Ackermann function
POW-5
Sample Solution to PS1, part I
21.3-21.4 (22.3-22.4) Handout

Oct 8
Union-Find contd.; Priority queues, binary search trees, splay trees

POW-6
Sample Solution to PS1, part II
Handout, 6 (7)

Oct 15
Greedy algorithms: Activity selection; Huffman encoding

2 due; 3 out Problem Set -3
16.1-16.4 (17.1-17.4)

Oct 22
Dynamic programming: Longest Common Subsequence; Application to shortest paths problems
POW-8
Sample Solution to PS2 15.3-15.4 (16.3-16.4)
24.1, 25.2 (25.3, 26.2)

Oct 29
Single-source and all-pairs shortest paths; Network flows: Maxflow-mincut theorem; Ford-Fulkerson algorithm 3 due; 4 out
POW-9
Problem Set -4
26.1-26.2 (27.1-27.2)

Nov 5
Network flows, contd. 4 due POW-10
Sample Solution to PS3
Sample Solution to PS4
26.4-26.5 (27.4-27.5)

Nov 12
Push-relabel algorithm for maxflow; Introduction to Linear programming: Formulating problems as LPs Midterm out
29

Nov 19 The geometry of LP and the simplex algorithm Midterm due; 5 out POW-12
Problem Set -5
29

Nov 26
Thanksgiving Day Eve: No class

Notes on LP

Dec 3
LP, contd; NP-completeness: P, NP, polynomial-time reductions
5 due; 6 out POW-13
Problem Set -6
34 (36)

Dec 10
NP-completeness, contd: polynomial-time reductions and proofs
6 due Sample Solution to PS5
Sample Solution to PS6 34 (36)

Dec 17
Final Exam

The reading assignments list sections and chapters of the second edition of the textbook. The numbers within the parenthesis are the corresponding sections and chapters in the first edition.

Note: All handouts are in PDF.

Week	Topic	Problem Sets	Handouts	Reading

Sep 10	Administrivia; Algorithms & their complexity; The Selection problem: Randomized linear-time algorithm	1 out	Problem Set -1 POW-1	9, 22.1-22.3 (10, 23.1-23.3)
Sep 17	Deterministic algorithm for selection; Introduction to graphs & graph algorithms;		POW-2 POW-3	9, 22.1-22.3 (10, 23.1-23.3)
Sep 24	Minimum spanning trees: Structural properties; Prim's & Kruskal's algorithms;	1 due; 2 out	POW-4 Problem Set -2	23 (24)
Oct 1	Data structures for disjoint sets: Union-find algorithms; Inverse Ackermann function		POW-5 Sample Solution to PS1, part I	21.3-21.4 (22.3-22.4) Handout
Oct 8	Union-Find contd.; Priority queues, binary search trees, splay trees		POW-6 Sample Solution to PS1, part II	Handout, 6 (7)
Oct 15	Greedy algorithms: Activity selection; Huffman encoding	2 due; 3 out	Problem Set -3	16.1-16.4 (17.1-17.4)
Oct 22	Dynamic programming: Longest Common Subsequence; Application to shortest paths problems		POW-8 Sample Solution to PS2	15.3-15.4 (16.3-16.4) 24.1, 25.2 (25.3, 26.2)
Oct 29	Single-source and all-pairs shortest paths; Network flows: Maxflow-mincut theorem; Ford-Fulkerson algorithm	3 due; 4 out	POW-9 Problem Set -4	26.1-26.2 (27.1-27.2)
Nov 5	Network flows, contd.	4 due	POW-10 Sample Solution to PS3 Sample Solution to PS4	26.4-26.5 (27.4-27.5)
Nov 12	Push-relabel algorithm for maxflow; Introduction to Linear programming: Formulating problems as LPs	Midterm out		29
Nov 19	The geometry of LP and the simplex algorithm	Midterm due; 5 out	POW-12 Problem Set -5	29
Nov 26	Thanksgiving Day Eve: No class		Notes on LP
Dec 3	LP, contd; NP-completeness: P, NP, polynomial-time reductions	5 due; 6 out	POW-13 Problem Set -6	34 (36)
Dec 10	NP-completeness, contd: polynomial-time reductions and proofs	6 due	Sample Solution to PS5 Sample Solution to PS6	34 (36)
Dec 17	Final Exam