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

## Time: MWF 10:30 - 11:50 Location: WeH 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: Chris Wang [ | Wean 3709 | 8-5182] :.. office hours: after each class, or by appointment. TA: Virginia Vassilevska [ | Wean 3706 | 8-1023] :.. office hours: after class or by appointment.

News:
• 5/03 Homework 5 Solution posted..
• 5/03 Page 1 of Final posted.
• 4/15 Homework 5 posted.
• 4/04 Here is the statistics for midterm 2.
• 3/31 Homework 3 is graded and new solution posted.
• 3/31 A solution to homework 4 has been posted. See below.
• 3/30 Here are the instructions (PS) for midterm 2. This midterm will focus mostly on NP-Completeness and Planarity.
• 3/30 We have not finished grading hw3. However, to help you study for the midterm, here is James, Jeff and Bryan's answers.
• 3/23 Homework 4 is out. It's due on March 30th.
• 2/23 Homework 3 is out. It's due on March 4th by e-mail.
• 2/14 Happy Valentine's Day! Here (PS) is the statistics for midterm 1, and the solution (PS) with some partial credit information.
• 2/06 Homework 1 solution is posted.
• 2/04 Practice midterm is posted.
• Homework 2 is due Feb. 7th by 11.59pm.
• We have created a mailing list for the class. You have not received a message, then you need to send us an email so we can add you.
• HOMEWORK 0: Many people did not use the correct definition for tree and subtree. A tree is an undirected connected acyclic graph. A subtree of a tree T=(V,E) is a tree T'=(V',E') where V' and E' are subsets of V and E respectively. Many people assumed we are talking about rooted trees. If you want to resubmit problem 7, do so before Wednesday.

• Homeworks: 10%
• Midterm 1: 25%
• Midterm 2: 30% (Covers mostly new material)
• Final exam: 35% (Covers all material)

Here is the approximate grading standard. (Subject to change)
• 95%: A+
• 85%: A
• 80%: A-
• 75%: B+
• 70%: B
• 65%: B-
• below 65%: C

## Books

• Official:
• Dexter C. Kozen, The Design and Analysis of Algorithms, Springer-Verlag, 1992.
• Optional:
• Thomas H. Cormen, Charles E. Leiserson, and Ronald L. Rivest, Introduction to Algorithms, MIT Press, 1990.
• Rajeev Motwani, Prabhakar Raghavan, Randomized Algorithms, Cambridge University Press, 1995.
• N. Alon and J. Spencer. The Probabilistic Method. Wiley Interscience, New York, 1992.

## Homeworks

• All homeworks are due at the beginning of class.
• We will not accept late submission. However, each group has a single 48 hours pass. This pass can be used to extend the deadline for one homework by 48 hours.
• You are encouraged to work in groups of 2 or (preferably) 3. The group should be as diverse as possible. (Exception: Homework 0 needs to be done individually.)
• Each group should submit a single write-up.
• All homeworks must be typed, preferably in LaTeX. Submit both paper copy in class, and digital version by e-mail to the TAs.
• A group earns 30% bonus to the entire homework for each solution posted on the class website. Submission in LaTeX will increase your chances.
• You can earn more than 100% on most problem sets. A score higher than 100% is bonus.
• If you use any reference or webpage, you must cite it.

## Tentative Schedule

 No. Date Topics Readings Homework 1 01/10 M Introduction, Algorithm, Complexity, Various Equalities, Graphs, Recursion Tree, Master Theorem, Akra-Bazzi Theorem, Divide and Conquer (Strassen, Binary Multiplication), Dynamic Programming, Breadth First Search, Topological Sort, Minimum Spanning Trees, Shortest Paths [Kozen 1] [CLR 1, 2, 3, 4, 5.4] Homework 0 (PS) Solution (PS) 2 01/12 W Hints, Depth First Search, Strongly Connected Components [Kozen 2, 4, 5] [CLR 23, 24, 25] 3 01/14 F More strongly connected components, minimum spanning forest [Kozen 4] [CLR 23, 24] 4 01/17 M (Martin Luther King Day) NO CLASS 5 01/19 W Union-Find, Analysis [Kozen 10,11] [CLR 22] Homework 0 Due. Homework 1 (PS) Solution (PS) 6 01/21 F Heaps, Binomial Heaps, Amortized Analysis of Binomial Heaps [Kozen 8] [CLR 20] 7 01/24 M Fibonacci Heaps [Kozen 9] [CLR 21] 8 01/26 W More Fibonacci Heaps [Kozen 9] [CLR 21] 9 01/28 F Treaps (Random Search Trees) [Kozen 13] [M&R 8.2] Homework 1 Due. Homework 2 (PS) Q1 picture Solution 10 01/31 M More Treaps [Kozen 13] 11 02/02 W Splay Trees [Kozen 12] Sleator's note 12 02/04 F Splay Trees Proof [Kozen 12] Practice Midterm Solution 13 02/07 M No class 14 02/09 W Midterm 1 -- Part 1 15 02/11 F Midterm 1 -- Part 2 16 02/14 M Planar Graphs, 5-coloring 17 02/16 W Planarity Testing [Kozen 14] 18 02/18 F Planar Separator Theorem 1 [Kozen 15] 19 02/21 M Subhash Khot's Talk (Attendence not required) 20 02/23 W Planar Separator Theorem 2 [Kozen 15] Homework 3 (PS) Solution 21 02/25 F Planar Separators [Kozen 15] 22 02/28 M NP-Completeness 1 (Introduction) [Kozen 21, 22, 23, 24] [CLR 36] 23 03/02 W NP-Completeness 2 (Random NP Problems) [Kozen 21, 22, 23, 24] [CLR 36] 24 03/04 F Mid-Semester Break; No Class 03/07 M ----------------- (Spring Break) 03/09 W ----------------- (Spring Break) 03/11 F ----------------- (Spring Break) 25 03/14 M NP-Completeness 3 (NP, co-NP, NP-hard, Independent Set) [Kozen 21, 22, 23, 24] [CLR 36] 26 03/16 W NP-Completeness 4 (Independent Set and Cook's Theorem) [Kozen 21, 22, 23, 24] [CLR 36] 27 03/18 F NP-Completeness 5 (Cook's Theorem) [Kozen 21, 22, 23, 24] [CLR 36] 28 03/21 M NP-Completeness 6 (Hamiltonian Cycle to SAT) [Kozen 21, 22, 23, 24] [CLR 36] 29 03/23 W Guest Lecturer: Anupam Gupta on Approximation Algorithms [CLR 37] Homework 4 (PS) Solution (PS) 30 03/25 F Randomized 2-SAT 31 03/28 M Polynomial identity checking [Kozen 40] [M&R 7.2] 32 03/30 W Polynomial identity checking [Kozen 40] [M&R 7.2] 33 04/01 F Midterm 2 34 04/04 M Matching [Kozen 19, 20] [M&R 7.3] 35 04/06 W RP, Randomized Algorithms -- Test of Associativity 36 04/08 F RP, Randomized Algorithms 37 04/11 M Random Walks -- 1, 2, and 3 dimensions [M&R 6] 38 04/13 W String and Set Equality 39 04/15 F No class (Spring Carnival) Homework 5 (PS) Solution 40 04/18 M Random Walks on General Graph [M&R 6] 41 04/20 W How to Write a Proof 42 04/22 F The probabilistic method - Max-Cut; Randomized and Deterministic 1/2-Approximation Algorithms for Max-Cut [M&R 5.1] 43 04/25 M Final Review by Chris and Virginia 45 04/27 W Free Cake: Cake Cutting 44 04/29 F "Sunny" Day, No Class 46 05/05  Thursday Final Exam. 8:30a.m. to 11:30a.m. DH 2302