Carnegie Mellon University, School of Computer Science

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

Time MWF 10:30am-11:20am
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 Bartosz Przydatek
[bartosz@cs | Wean 4126 | 8-1188]
office hours: Tu, Th 4:30pm-5:30pm
Textbooks
Web page http://www.cs.cmu.edu/afs/cs.cmu.edu/academic/class/15750-s02/www/
News group cmu.cs.class.cs750
Other references
  • 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.

Statistical data

Tentative schedule

No. DateTopicsReadingsHomework
1 01/14 MHeaps [Kozen 1-5]
[Cormen et al, 7]
2 01/16 WBinomial Heaps [Kozen 8, MR 8.1]
3 01/18 FAmortized Analysis [Kozen 8]
[Sleator's notes]		#1 out
4 01/21 MDijkstra's SSSP, Fibonacci Heaps [Kozen 9]
5 01/23 WFibonacci Heaps (cont.) [Kozen 10]
6 01/25 FUnion-Find [Kozen 11]#1 due, #1 sol., #2 out
7 01/28 MUnion-Find (cont.) [Kozen 12]
8 01/30 WSplay Trees [Kozen 12]
9 02/01 FAnalysis of Splay Trees[Sleator's notes]#2 due, #2 sol., #3 out
10 02/04 MRandom Search Trees [Kozen 13]
11 02/06 WPlanar and Plane Graphs [Kozen 14]
12 02/08 FThe Planar Separator Theorem [Kozen 15]#3 due, #3 sol., #4 out
13 02/11 MMax Flow [Kozen 16]
14 02/13 WMore on Max Flow [Kozen 17, MR 10.2]
15 02/15 FStill More on Max Flow [Kozen 18]#4 due, #4 sol.
16 02/18 MRecap: Analysis of Union-Find [Kozen 12]
17 02/20 WReview [Kozen 1-18]
18 02/22 FFirst midterm exam
19 02/25 MMatching [Kozen 19]
20 02/27 WMore on Matching [Kozen 19]
21 03/01 FStill more on Matching[Kozen 20]#5 out
22 03/04 MMarkov Chains and Random Walks [MR 6.1-6.3]
03/06 WMarkov Chains and Random Walks [MR 6.4]#5 due, #5 sol., #6 out
03/08 F----------------- (midterm break)
23 03/11 MMarkov Chains and Random Walks [MR 6.5]
24 03/13 WMarkov Chains and Random Walks [MR 6.6]
25 03/15 FProblems & Puzzles #6 due, #6 sol., #7 out
26 03/18 MMarkov Chains and Random Walks [MR 6.7]
27 03/20 WMarkov Chains and Random Walks (cont.) [MR 6.7]
28 03/22 FApproximate Counting [MR 11.1-11.2]#7 due, #7 sol.
29 03/25 MMarkov Chains and Random Walks [MR 6.8]
30 03/27 WReview [MR 6, 11.1-11.2]
31 03/29 FSecond midterm exam
04/01 M----------------- (spring break)
04/03 W----------------- (spring break)
04/05 F----------------- (spring break)
32 04/08 MAlgebraic Techniques [MR 7.1-7.2]
33 04/10 WAlgebraic Techniques [MR 7.3]
34 04/12 FAlgebraic Techniques [MR 7.4-7.6]#8 out
35 04/15 MNumber Theory and Algebra: Intro, Primality tests [MR 14.1-2, 14.6]
36 04/17 WNumber Theory: Dartboard method [Bach's Thesis]
04/19 F----------------- (spring carnival) #8 due, #8 sol., #9 out
37 04/22 MData Structures: Universal hashing [MR 8.4]
38 04/24 WData Structures: Universal hashing (cont.)[MR 8.4]
39 04/26 FCryptographic hash functions [notes]#9 due, #9 sol.
40 04/29 MNumber Theory: gcd & continued fractions[MR 14.3, MathWorld]
[Knott's notes]
41 05/01 WNumber Theory: factoring polynomials (LLL-algorithm)[Sudan's notes]
42 05/03 FNumber Theory: LLL (cont.)/ Review[Sudan's notes]
05/06 MFinal exam
last update: May 1, 2002 maintained by Bartosz Przydatek (bartosz@cs.cmu.edu)