15-750 Graduate Algorithms (Spring 2005) (original) (raw)
No.
Date
Topics
Readings
Homework
1
01/10 M
Introduction, Algorithm, Complexity, Various Equalities, Graphs, Recursion Tree, Master Theorem, Akra-Bazzi Theorem, Divide and Conquer (Strassen, Binary Multiplication), Dynamic Programming, Breadth First Search, Topological Sort, Minimum Spanning Trees, Shortest Paths
[Kozen 1] [CLR 1, 2, 3, 4, 5.4]
2
01/12 W
Hints, Depth First Search, Strongly Connected Components
[Kozen 2, 4, 5] [CLR 23, 24, 25]
3
01/14 F
More strongly connected components, minimum spanning forest
[Kozen 4] [CLR 23, 24]
4
01/17 M
(Martin Luther King Day) NO CLASS
5
01/19 W
Union-Find, Analysis
[Kozen 10,11] [CLR 22]
Homework 0 Due. Homework 1 (PS) Solution (PS)
6
01/21 F
Heaps, Binomial Heaps, Amortized Analysis of Binomial Heaps
[Kozen 8] [CLR 20]
7
01/24 M
Fibonacci Heaps
[Kozen 9] [CLR 21]
8
01/26 W
More Fibonacci Heaps
[Kozen 9] [CLR 21]
9
01/28 F
Treaps (Random Search Trees)
[Kozen 13] [M&R 8.2]
Homework 1 Due. Homework 2 (PS) Q1 picture Solution
10
01/31 M
More Treaps
[Kozen 13]
11
02/02 W
Splay Trees
[Kozen 12] Sleator's note
12
02/04 F
Splay Trees Proof
[Kozen 12]
13
02/07 M
No class
14
02/09 W
Midterm 1 -- Part 1
15
02/11 F
Midterm 1 -- Part 2
16
02/14 M
Planar Graphs, 5-coloring
17
02/16 W
Planarity Testing
[Kozen 14]
18
02/18 F
Planar Separator Theorem 1
[Kozen 15]
19
02/21 M
Subhash Khot's Talk (Attendence not required)
20
02/23 W
Planar Separator Theorem 2
[Kozen 15]
21
02/25 F
Planar Separators
[Kozen 15]
22
02/28 M
NP-Completeness 1 (Introduction)
[Kozen 21, 22, 23, 24] [CLR 36]
23
03/02 W
NP-Completeness 2 (Random NP Problems)
[Kozen 21, 22, 23, 24] [CLR 36]
24
03/04 F
Mid-Semester Break; No Class
03/07 M
----------------- (Spring Break)
03/09 W
----------------- (Spring Break)
03/11 F
----------------- (Spring Break)
25
03/14 M
NP-Completeness 3 (NP, co-NP, NP-hard, Independent Set)
[Kozen 21, 22, 23, 24] [CLR 36]
26
03/16 W
NP-Completeness 4 (Independent Set and Cook's Theorem)
[Kozen 21, 22, 23, 24] [CLR 36]
27
03/18 F
NP-Completeness 5 (Cook's Theorem)
[Kozen 21, 22, 23, 24] [CLR 36]
28
03/21 M
NP-Completeness 6 (Hamiltonian Cycle to SAT)
[Kozen 21, 22, 23, 24] [CLR 36]
29
03/23 W
Guest Lecturer: Anupam Gupta on Approximation Algorithms
[CLR 37]
30
03/25 F
Randomized 2-SAT
31
03/28 M
Polynomial identity checking
[Kozen 40] [M&R 7.2]
32
03/30 W
Polynomial identity checking
[Kozen 40] [M&R 7.2]
33
04/01 F
Midterm 2
34
04/04 M
Matching
[Kozen 19, 20] [M&R 7.3]
35
04/06 W
RP, Randomized Algorithms -- Test of Associativity
36
04/08 F
RP, Randomized Algorithms
37
04/11 M
Random Walks -- 1, 2, and 3 dimensions
[M&R 6]
38
04/13 W
String and Set Equality
39
04/15 F
No class (Spring Carnival)
40
04/18 M
Random Walks on General Graph
[M&R 6]
41
04/20 W
42
04/22 F
The probabilistic method - Max-Cut; Randomized and Deterministic 1/2-Approximation Algorithms for Max-Cut
[M&R 5.1]
43
04/25 M
Final Review by Chris and Virginia
45
04/27 W
Free Cake: Cake Cutting
44
04/29 F
"Sunny" Day, No Class
46
05/05 Thursday
Final Exam. 8:30a.m. to 11:30a.m. DH 2302