Time  MWF 10:30am11:20am 
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  Bartosz Przydatek [bartosz@cs  Wean 4126  81188] office hours: Tu, Th 4:30pm5:30pm 
Textbooks  
Web page  http://www.cs.cmu.edu/afs/cs.cmu.edu/academic/class/15750s02/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.
No.  Date  Topics  Readings  Homework 
1  01/14 M  Heaps  [Kozen 15] [Cormen et al, 7]  
2  01/16 W  Binomial Heaps  [Kozen 8, MR 8.1]  
3  01/18 F  Amortized Analysis  [Kozen 8] [Sleator's notes]  #1 out 
4  01/21 M  Dijkstra's SSSP, Fibonacci Heaps  [Kozen 9]  
5  01/23 W  Fibonacci Heaps (cont.)  [Kozen 10]  
6  01/25 F  UnionFind  [Kozen 11]  #1 due, #1 sol., #2 out 
7  01/28 M  UnionFind (cont.)  [Kozen 12]  
8  01/30 W  Splay Trees  [Kozen 12]  
9  02/01 F  Analysis of Splay Trees  [Sleator's notes]  #2 due, #2 sol., #3 out 
10  02/04 M  Random Search Trees  [Kozen 13]  
11  02/06 W  Planar and Plane Graphs  [Kozen 14]  
12  02/08 F  The Planar Separator Theorem  [Kozen 15]  #3 due, #3 sol., #4 out 
13  02/11 M  Max Flow  [Kozen 16]  
14  02/13 W  More on Max Flow  [Kozen 17, MR 10.2]  
15  02/15 F  Still More on Max Flow  [Kozen 18]  #4 due, #4 sol. 
16  02/18 M  Recap: Analysis of UnionFind  [Kozen 12]  
17  02/20 W  Review  [Kozen 118]  
18  02/22 F  First midterm exam  
19  02/25 M  Matching  [Kozen 19]  
20  02/27 W  More on Matching  [Kozen 19]  
21  03/01 F  Still more on Matching  [Kozen 20]  #5 out 
22  03/04 M  Markov Chains and Random Walks  [MR 6.16.3]  
03/06 W  Markov Chains and Random Walks  [MR 6.4]  #5 due, #5 sol., #6 out  
03/08 F   (midterm break)  
23  03/11 M  Markov Chains and Random Walks  [MR 6.5]  
24  03/13 W  Markov Chains and Random Walks  [MR 6.6]  
25  03/15 F  Problems & Puzzles  #6 due, #6 sol., #7 out  
26  03/18 M  Markov Chains and Random Walks  [MR 6.7]  
27  03/20 W  Markov Chains and Random Walks (cont.)  [MR 6.7]  
28  03/22 F  Approximate Counting  [MR 11.111.2]  #7 due, #7 sol. 
29  03/25 M  Markov Chains and Random Walks  [MR 6.8]  
30  03/27 W  Review  [MR 6, 11.111.2]  
31  03/29 F  Second midterm exam  
04/01 M   (spring break)  
04/03 W   (spring break)  
04/05 F   (spring break)  
32  04/08 M  Algebraic Techniques  [MR 7.17.2]  
33  04/10 W  Algebraic Techniques  [MR 7.3]  
34  04/12 F  Algebraic Techniques  [MR 7.47.6]  #8 out 
35  04/15 M  Number Theory and Algebra: Intro, Primality tests  [MR 14.12, 14.6]  
36  04/17 W  Number Theory: Dartboard method  [Bach's Thesis]  
04/19 F   (spring carnival)  #8 due, #8 sol., #9 out  
37  04/22 M  Data Structures: Universal hashing  [MR 8.4]  
38  04/24 W  Data Structures: Universal hashing (cont.)  [MR 8.4]  
39  04/26 F  Cryptographic hash functions  [notes]  #9 due, #9 sol. 
40  04/29 M  Number Theory: gcd & continued fractions  [MR 14.3, MathWorld] [Knott's notes]  
41  05/01 W  Number Theory: factoring polynomials (LLLalgorithm)  [Sudan's notes]  
42  05/03 F  Number Theory: LLL (cont.)/ Review  [Sudan's notes]  
05/06 M  Final exam 
last update: May 1, 2002  maintained by Bartosz Przydatek (bartosz@cs.cmu.edu) 