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
[ | Wean 4113 | 8-3742]
office hours: after each class, until there are no more questions
Secretary Phyllis Pomerantz
[ | Wean 4610 | 8-7897]
TA Doru Balcan
[ | Wean 3715 | 8-1405]
office hours: by appointment
Web page
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"



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)
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),

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

01/28 W [No class today]

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

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
02/20 F First midterm exam - grades histogram

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

02/25 W Matching.

02/27 F [No class today]

03/01 M More matching. Reductions and NP Complete Problems Kozen (Ch. 20,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

03/24 W Counting Problems and #P Kozen (Ch. 26)
03/26 F [No class today]

03/29 M Counting bipartite matchings
Kozen (Ch. 27)

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

MT2 04/02 F Second midterm exam - grades histogram

04/05 M On a string-counting problem

04/07 W Approximation Algs (II) Motwani
32 04/09 F More Approximation Algs
33 04/12 M Probability and Randomness. Chernoff Bounds
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.
37 04/23 F Review

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

04/30 F Cake Cutting Problem
[here we should see Algorithms-on-their-best-behavior]
Google, W. Hively

05/03 M
Final exam -  08:30am - 11:30am DH 1212 - grades histogram

last update: May 10, 2004 maintained by Doru Balcan (