Carnegie Mellon University, School of Computer Science

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

Time MWF 10:30am-11:50am
Location Wean 5409
Instructor Manuel Blum
[mailto:mblum+@cs.cmu.edu | Wean 4113 | 8-3742]
office hours: after each class, until there are no more questions
Secretary Phyllis Pomerantz
[mailto:plp+@cs.cmu.edu | Wean 4610 | 8-7897]
TA Doru Balcan
[mailto:dbalcan@cs.cmu.edu | Wean 3715 | 8-1405]
office hours: by appointment
Textbook
Web page http://www.cs.cmu.edu/afs/cs.cmu.edu/academic/class/15750-s04/www/
News group cmu.cs.class.cs750
Other references
  • Noga Alon,   Joel Spencer, "The Probabilistic Method"
  • A. Borodin,  R. El-Yaniv, "Online Computation and Competitive Analysis"
  • G. Brassard, P. Bratley, "Algorithmics : Theory and Practice"
  • T. H. Cormen, C. E. Leiserson, R. L. Rivest, "Introduction to Algorithms"
    - The standard text.
  • S. Even, "Graph Algorithms"
  • M. R. Garey, D. S. Johnson, "Computers and Intractability : A Guide to the Theory of NP-Completeness"
    - Beautifully and clearly written.
  • D. E. Knuth "The Art of Computer Programming",
    vol. 2 (Seminumerical Algorithms) & vol. 3 (Sorting and Searching)
    - Important and standard reference.
  • U. Manber, "Introduction to Algorithms: A Creative Approach"
    - An excellent book for learning how to create algorithms.
  • R. E. Tarjan, "Data Structures and Network Algorithms"
    - Tarjan is the master of algorithms.
  • V. Vazirani, "Approximation Algorithms"

Grading

Homeworks

There will be weekly homework assignments, usually consisting of 3-4 problems presented in the class during each week. Every homework will be due one week after the it's posted, in class.

You are encouraged to work in groups of two or (preferably) three people. Each group should turn in a single write-up. 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.

News (4/21/2004) The last year's final exam is here. After you take your time and work it through, you may get some feedback by looking at the solutions.
News (5/10/2004) The final exam papers are available for you to take a last look at.(Unfortunately, we can't give them to you for good, because of the regulations.) Please pick them up in person, at Doru's office (We3715).We would like to congratulate you all for your performance, both individual, and as a team. 

Tentative schedule

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 Union-Find  Kozen (Ch. 10),

7
 01/26 M Analysis of Union-Find (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 Self-Organizing 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,3-5,8-15)
 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 NP-completeness
 Kozen (Ch. 21-25), 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 string-counting 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 MAX-SAT (&co.) [guest lecturer Avrim Blum] A.Blum- lecture notes
40
 04/30 F Cake Cutting Problem
[here we should see Algorithms-on-their-best-behavior] 		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)