15-750 Graduate Algorithms (Spring 2005)
Prof. Manuel Blum



News:

Grading


Here is the approximate grading standard. (Subject to change)

Books


Homeworks



Tentative Schedule

No. DateTopicsReadingsHomework
1 01/10 MIntroduction, 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]Homework 0 (PS) Solution (PS)
2 01/12 WHints, Depth First Search, Strongly Connected Components [Kozen 2, 4, 5] [CLR 23, 24, 25]
3 01/14 FMore strongly connected components, minimum spanning forest [Kozen 4] [CLR 23, 24]
4 01/17 M(Martin Luther King Day) NO CLASS
5 01/19 WUnion-Find, Analysis[Kozen 10,11] [CLR 22]Homework 0 Due. Homework 1 (PS) Solution (PS)
6 01/21 FHeaps, Binomial Heaps, Amortized Analysis of Binomial Heaps[Kozen 8] [CLR 20]
7 01/24 MFibonacci Heaps[Kozen 9] [CLR 21]
8 01/26 WMore Fibonacci Heaps[Kozen 9] [CLR 21]
9 01/28 FTreaps (Random Search Trees)[Kozen 13] [M&R 8.2]Homework 1 Due. Homework 2 (PS) Q1 picture Solution
10 01/31 MMore Treaps[Kozen 13]
11 02/02 WSplay Trees [Kozen 12] Sleator's note
12 02/04 FSplay Trees Proof[Kozen 12]Practice Midterm Solution
13 02/07 MNo class
14 02/09 WMidterm 1 -- Part 1
15 02/11 FMidterm 1 -- Part 2
16 02/14 MPlanar Graphs, 5-coloring
17 02/16 WPlanarity Testing[Kozen 14]
18 02/18 FPlanar Separator Theorem 1[Kozen 15]
19 02/21 MSubhash Khot's Talk (Attendence not required)
20 02/23 WPlanar Separator Theorem 2[Kozen 15]Homework 3 (PS) Solution
21 02/25 FPlanar Separators[Kozen 15]
22 02/28 MNP-Completeness 1 (Introduction)[Kozen 21, 22, 23, 24] [CLR 36]
23 03/02 WNP-Completeness 2 (Random NP Problems)[Kozen 21, 22, 23, 24] [CLR 36]
24 03/04 FMid-Semester Break; No Class
03/07 M----------------- (Spring Break)
03/09 W----------------- (Spring Break)
03/11 F----------------- (Spring Break)
25 03/14 MNP-Completeness 3 (NP, co-NP, NP-hard, Independent Set) [Kozen 21, 22, 23, 24] [CLR 36]
26 03/16 WNP-Completeness 4 (Independent Set and Cook's Theorem)[Kozen 21, 22, 23, 24] [CLR 36]
27 03/18 FNP-Completeness 5 (Cook's Theorem)[Kozen 21, 22, 23, 24] [CLR 36]
28 03/21 MNP-Completeness 6 (Hamiltonian Cycle to SAT)[Kozen 21, 22, 23, 24] [CLR 36]
29 03/23 WGuest Lecturer: Anupam Gupta on Approximation Algorithms[CLR 37]Homework 4 (PS) Solution (PS)
30 03/25 FRandomized 2-SAT
31 03/28 MPolynomial identity checking[Kozen 40] [M&R 7.2]
32 03/30 WPolynomial identity checking[Kozen 40] [M&R 7.2]
33 04/01 FMidterm 2
34 04/04 MMatching[Kozen 19, 20] [M&R 7.3]
35 04/06 WRP, Randomized Algorithms -- Test of Associativity
36 04/08 FRP, Randomized Algorithms
37 04/11 MRandom Walks -- 1, 2, and 3 dimensions[M&R 6]
38 04/13 WString and Set Equality
39 04/15 FNo class (Spring Carnival) Homework 5 (PS) Solution
40 04/18 MRandom Walks on General Graph[M&R 6]
41 04/20 WHow to Write a Proof
42 04/22 FThe probabilistic method - Max-Cut; Randomized and Deterministic 1/2-Approximation Algorithms for Max-Cut[M&R 5.1]
43 04/25 MFinal Review by Chris and Virginia
45 04/27 WFree Cake: Cake Cutting
44 04/29 F"Sunny" Day, No Class
46 05/05  ThursdayFinal Exam. 8:30a.m. to 11:30a.m. DH 2302


last modified: March 22 2005