Time  MWF 10:30am11:50am 
Location  Wean 5409 
Instructor  Manuel Blum [mailto:mblum+@cs.cmu.edu  Wean 4113  83742] office hours: after each class, until there are no more questions 
Secretary  Phyllis
Pomerantz [mailto:plp+@cs.cmu.edu  Wean 4610  87897] 
TA  Doru Balcan [mailto:dbalcan@cs.cmu.edu  Wean 3715  81405] office hours: by appointment 
Textbook  
Web page  http://www.cs.cmu.edu/afs/cs.cmu.edu/academic/class/15750s04/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 going 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 (average)
score on the chosen problem(s) times the number of problems solved.
No.  Date  Topics  Readings  Homework 
1  01/12 M  Intro. DFS
& BFS. 
Kozen (Ch.1; Ch. 4) 

2  01/14 W  Matroids and
Independence 
Kozen (Ch.2: 2.1, 2.2; Ch.3) 
HW1 
3  01/16 F  Heaps. Binomial Heaps.  Kozen (Ch.8: 8.1, 8.3), Vuillemin78 

4  01/19 M  Amortized Analysis.  D.
Sleator, Kozen (Ch.8: 8.2) 

5  01/21 W  Fibonacci Heaps.  Kozen (Ch. 9), Fredman&Tarjan87 
HW1
sol, HW2

6  01/23 F  UnionFind  Kozen (Ch. 10), 

7 
01/26 M  Analysis of
UnionFind (postponed) [No class today] 
Kozen (Ch. 11), Tarjan&vanLeeuwen84,
LaPoutré96 

8 
01/28 W  [No class
today] 

9 
01/30 F  Splay Trees.
[incl. Analysis of ST] 
Kozen (Ch. 12)  HW2_sol, HW3 
10 
02/02 M  SelfOrganizing
Data Structures [guest lecturer Danny Sleator] 
D.Sleator,
Albers&Westbrook98 

11 
02/04 W  Random Search Trees  Kozen (Ch. 13), Seidel&Aragon96  
12  02/06 F  Plane and Planar Graphs  Kozen (Ch. 14) 
HW3_sol, HW4 
13  02/09 M  Planarity Testing Algorithm  Kozen (Ch. 14), Hopcroft&Tarjan74 

14  02/11 W  Planar Separator Theorem  Kozen (Ch. 15), Lipton&Tarjan79 

15  02/13 F  Planar
Separator Theorem (II) 
Kozen (Ch. 15) 

02/16 M  President's Day; No Classes 

16  02/18 W  Review 
Kozen (Ch. 1,35,815) 
HW4
sol 
MT1 
02/20 F  First midterm exam  grades histogram 

17  02/23 M  [Doru will
answer questions about exam] 

18 
02/25 W  Matching. 
Kozen 

19 
02/27 F  [No class
today] 

20 
03/01 M  More matching. Reductions and NP Complete Problems  Kozen (Ch. 20,21) 

21 
03/03 W  More NP Complete Problems  Kozen (Ch 21,22) 

03/05 F   (midterm break)  
03/08 M   (spring break)  
03/10 W   (spring break)  
03/12 F   (spring break)  
22  03/15 M  Even more NP Complete Problems  Kozen (Ch 23)  HW5 
23  03/17 W  Still more NP Complete Problems  Kozen (Ch. 24) 

24  03/19 F  Cook's Theorem  Kozen (Ch. 25) 

25  03/22 M  Review of
Reductions and NPcompleteness 
Kozen (Ch. 2125), Garey&Johnson 

26 
03/24 W  Counting Problems and #P  Kozen (Ch. 26)  
27 
03/26 F  [No class today]  
28 
03/29 M  Counting
bipartite matchings 
Kozen (Ch. 27) 

29 
03/31 W  Approximation Algs.+Review  Motwani,
Vazirani, Kann&Crescenzi 

MT2  04/02 F  Second
midterm exam  grades histogram 

30 
04/05 M  On a stringcounting problem 

31 
04/07 W  Approximation Algs (II)  Motwani  
32  04/09 F  More
Approximation
Algs 
Motwani  
33  04/12 M  Probability
and Randomness. Chernoff Bounds 
Alon&Spencer  
34  04/14 W  [No class
today] 

04/16 F   (Spring Carnival); No Classes  
35  04/19 M  Random Walks  Pólya's Theorem. "Bits on forehead"  Brassard&Bratley  
36  04/21 W  Random Walks on Graphs.  HW6 

37  04/23 F  Review 

38 
04/26 M  The Probabilistic Method  Alon&Spencer  
39 
04/28 W  Approximation Algorithms for MAXSAT (&co.) [guest lecturer Avrim Blum]  A.Blum lecture
notes 

40 
04/30 F  Cake
Cutting Problem [here we should see Algorithmsontheirbestbehavior] 
Google,
W.
Hively 

FE 
05/03
M 
Final exam 
08:30am  11:30am DH 1212  grades histogram 
last update: May 10, 2004  maintained by Doru Balcan (dbalcan@cs.cmu.edu) 