Time  MWF 10:30am11:50am 
Location  Wean 5409 
Instructor  Manuel Blum [mblum@cs  Wean 4113  83742] office hours: after each class, until there are no more questions 
Secretary  Phyllis Pomerantz [plp@cs  Wean 4610  87897] 
TA  Ryan Williams [ryanw@cs  Wean 8203  83562] office hours: Tuesdays and Thursdays, 3pm4pm; or email for appointment 
Textbook  
Web page  http://www.cs.cmu.edu/afs/cs.cmu.edu/academic/class/15750s03/www/ 
News group  cmu.cs.class.cs750 
Other references 

You are encouraged to work in groups of two or (preferably) three people. Each group should turn in a single writeup. Homework grading is likely to be randomized: instead of grading all problems on an assignment, only one or two randomly chosen problems will be graded, and your total score on the assignment will be equal to the score on the chosen problem(s) times the number of problems solved.
Please note:
Homework  Avg.  Std.Dev. 
1  28.4  1.6 
2  28.5  2.3 
3  26.8  7.3 
4  18  1.7 
5  27.5  4.3 
6  27.4  4 
No.  Date  Topics  Readings  Homework 
1  01/13 M  Intro, Strassen's Alg  [Kozen 1]  
2  01/15 W  Topological Sort  [Kozen 2]  
3  01/17 F  Min Spanning Trees  [Kozen 2.1, 2.2]  
4  01/20 M  Matroids  [Kozen 3]  
5  01/22 W  More Matroids  [Kozen 3]  
6  01/24 F  Even More Matroids  [Kozen 3]  HW1 out 
7  01/27 M  Shortest Paths  [Kozen 5, 6, 7]  
8  01/29 W  Binomial Heaps  [Kozen 8.1]  
9  01/31 F  Amortized Analysis of Binomial Heaps  [Kozen 8.2], Sleator's notes  HW1 due, HW2 out 
10  02/03 M  " "  [Kozen 8.3]  
11  02/05 W  Fibonacci Heaps  [Kozen 9]  
12  02/07 F  Eager Meld in O(1), More Fibonacci  [Kozen 9]  HW2 due, HW3 out 
13  02/10 M  Even More Fibonacci  [Kozen 9]  
14  02/13 W  UnionFind 1  [Kozen 10]  
15  02/14 F  UnionFind 2  "  HW3 due, HW4 out 
16  02/17 M  More on UnionFind  [Kozen 11]  
17  02/19 W  Still More on UnionFind  "  
18  02/21 F  OhGodNotAgain! UnionFind  "  
19  02/24 M  Splay Trees  [Kozen 12]  
20  02/26 W  More Splay Trees  [Kozen 12]  Last year's midterm + solutions 
21  02/28 F  First midterm exam  
22  03/03 M  Treaps  [Kozen 13]  
03/05 W  More Treaps  [Kozen 13]  
03/07 F   (midterm break)  
23  03/10 M  Planar Graphs  [Kozen 14]  
24  03/12 W  Planarity Testing  [Hopcroft & Tarjan's paper]  
25  03/14 F  Planar Separator Theorem  [Kozen 15]  
26  03/17 M  Planar Separator Theorem 2  [Kozen 15]  HW5 out 
27  03/19 W  ??  [Kozen 27]  
28  03/21 F  ??  [Kozen 28]  
03/24 M   (spring break)  
03/26 W   (spring break)  
03/28 F   (spring break)  
29  03/31 M  Randomized Algorithms  Karger's Min Cut  [Motwani and Raghavan 1.11.2, 10.2]  HW5 due 
30  04/02 W  Rand. Algs. for 2SAT and 3SAT  [Motwani and Raghavan 6.1]  
31  04/04 F  Second midterm exam  
32  04/07 M  Random Walks 1, 2, and 3 dimensions  
33  04/09 W  More Examples with Randomness    
34  04/11 F   (spring carnival)    
35  04/14 M  Random Walks on Undirected Graphs  
36  04/16 W  Cover Times for Random Walks  HW6 out  
04/18 F  Commute Times  
37  04/21 M  Random lecture on Random Walks  
38  04/23 W  Class cancelled due to Sudafed  HW6 due  
39  04/25 F  ??  
40  04/28 M  Review for final  
41  04/30 W  The probabilistic method  
42  05/02 F  Dominating sets, randomly or greedily  
05/09  Final exam (8:30am11:30am) 
last update: Jan 9, 2002  "maintained" by Ryan Williams (ryanw@cs.cmu.edu) 