Carnegie Mellon University, School of Computer Science

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

Final grades are available. Email Ryan if you're curious.
The mean/median on the final was around 44-46 out of 61 (about 75%). The scores were pretty spread-out, from 50% to 100%.

If you're bored out of your mind and/or you're considering arguing over your score, I wrote up a short text file outlining what was possibly the most complicated grading scheme ever devised for a multiple choice exam.
Wow! A solution! Here's a solution to problem 2 on HW6. It's a simple example of an expected polynomial time algorithm that always returns the correct answer.


Time MWF 10:30am-11:50am
Location Wean 5409
Instructor Manuel Blum
[mblum@cs | Wean 4113 | 8-3742]
office hours: after each class, until there are no more questions
Secretary Phyllis Pomerantz
[plp@cs | Wean 4610 | 8-7897]
TA Ryan Williams
[ryanw@cs | Wean 8203 | 8-3562]
office hours: Tuesdays and Thursdays, 3pm-4pm; or email for appointment
Textbook
Web page http://www.cs.cmu.edu/afs/cs.cmu.edu/academic/class/15750-s03/www/
News group cmu.cs.class.cs750
Other references
  • R. Motwani, P. Raghavan, "Randomized Algorithms"
  • 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.

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 on Friday (in the class), one week after you've seen its last problem.

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 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:

Statistical data

Check it out: real bonafide statistical data. Enjoy.
(The first midterm stats will be available as soon as Manuel's calculator extracts them.)

First midterm: Mean = ??, Std. Dev. = ??

Second midterm: Mean = 86.4, Std. Dev. = 18.5

HomeworkAvg.Std.Dev.
1 28.41.6
2 28.52.3
3 26.87.3
4 181.7
5 27.54.3
6 27.44

Tentative schedule (which is being corrected as we go along)

[There are question marks where I (Ryan) forgot what we covered. Emails helping me out are most welcome.]

No. DateTopicsReadingsHomework
1 01/13 MIntro, Strassen's Alg [Kozen 1]
2 01/15 WTopological Sort [Kozen 2]
3 01/17 FMin Spanning Trees [Kozen 2.1, 2.2]
4 01/20 MMatroids [Kozen 3]
5 01/22 WMore Matroids [Kozen 3]
6 01/24 FEven More Matroids [Kozen 3]HW1 out
7 01/27 MShortest Paths[Kozen 5, 6, 7]
8 01/29 WBinomial Heaps [Kozen 8.1]
9 01/31 FAmortized Analysis of Binomial Heaps[Kozen 8.2], Sleator's notesHW1 due, HW2 out
10 02/03 M " " [Kozen 8.3]
11 02/05 WFibonacci Heaps [Kozen 9]
12 02/07 FEager Meld in O(1), More Fibonacci[Kozen 9]HW2 due, HW3 out
13 02/10 MEven More Fibonacci [Kozen 9]
14 02/13 WUnion-Find 1[Kozen 10]
15 02/14 FUnion-Find 2"HW3 due, HW4 out
16 02/17 MMore on Union-Find[Kozen 11]
17 02/19 WStill More on Union-Find "
18 02/21 FOh-God-Not-Again! Union-Find "
19 02/24 MSplay Trees[Kozen 12]
20 02/26 WMore Splay Trees [Kozen 12] Last year's midterm + solutions
21 02/28 FFirst midterm exam
22 03/03 MTreaps [Kozen 13]
03/05 WMore Treaps [Kozen 13]
03/07 F----------------- (midterm break)
23 03/10 MPlanar Graphs[Kozen 14]
24 03/12 WPlanarity Testing [Hopcroft & Tarjan's paper]
25 03/14 FPlanar Separator Theorem [Kozen 15]
26 03/17 MPlanar 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 MRandomized Algorithms -- Karger's Min Cut[Motwani and Raghavan 1.1-1.2, 10.2]HW5 due
30 04/02 WRand. Algs. for 2-SAT and 3-SAT[Motwani and Raghavan 6.1]
31 04/04 FSecond midterm exam
32 04/07 MRandom Walks-- 1, 2, and 3 dimensions
33 04/09 WMore Examples with Randomness -
34 04/11 F----------------- (spring carnival) -
35 04/14 MRandom Walks on Undirected Graphs
36 04/16 WCover Times for Random Walks HW6 out
04/18 FCommute Times
37 04/21 MRandom lecture on Random Walks
38 04/23 W Class cancelled due to Sudafed HW6 due
39 04/25 F??
40 04/28 MReview for final
41 04/30 WThe probabilistic method
42 05/02 FDominating sets, randomly or greedily
05/09 Final exam (8:30am-11:30am)
last update: Jan 9, 2002 "maintained" by Ryan Williams (ryanw@cs.cmu.edu)