CMU 15-451, Spring 2007

Instructor: Manuel Blum

TAs: Brent Bryan, Elisabeth Crawford, Michelle Goodstein, and Virginia Vassilevska

Notes about the final

The final for 15451 will be on Tues. May 8 from 5:30pm to 8:30pm in Porter Hall 100. Some reminders before the test:
• You will be allowed one note sheet, double-sided for the final.
• All electronic devices (including calculators) must be put away during the final. This means that you will not be able to use your cell phone to check the time, etc. We will write the time on the board.
• The final is a 3 hour, comprehensive test. There is an error in the notes saying that some material may not be on the final; that referred to last semester's class. *ALL* material in the notes, brought up in section, or in class is fair game for the final, with the exception of the machine learning lecture (#28 in the packet).
• Michelle will be holding extra office hours on Monday for all your last minute questions. She will be in her office (Wean 4126) from 3 to 4:30pm on Monday.

Announcements

• 05/04: Full solutions to homework 5 have been posted
• 05/04: Cake cutting lecture notes have been updated
• 05/01: Lecture notes have been updated through the end of the semester. Note that we skipped lecture 28
• 05/01: Final next Tuesday, May 8th.

General info

• Lectures: Tue/Thu 12-1:20, WeH 7500. Please note the room change!!!
• Recitations: Wed 1:30(Michelle)/2:30(Elisabeth and Virginia)/3:30(Brent). (A in DH 1211; B in SH 214, C in SH 220).
• Course information Updated on February 2 after class to clarify late policy for written homework.
• Schedule Updated on February 8th to reflect change in quiz date.
• Office hours are posted as of January 25; see the Course information
• The course bboards are: academic.cs.15-451 (for announcements) and academic.cs.15-451.discuss (for general discussion).

Minis

• 01/16: Mini 1 is available, and due by midnight on January 23rd. Please use subject line "15-451 MINI #1" so that the email is properly routed to your TA.
• 01/30: Mini 2 is available, and due by midnight on February 6th. Please use subject line "15-451 MINI #2" so that the email is properly routed to your TA and follow the other instructions for submission.
• 02/13: Mini 3 is available, and due by midnight on February 20th. Please use subject line "15-451 MINI #3" so that the email is properly routed to your TA and follow the other instructions for submission.
• 03/27: Mini 4 is available, and due by midnight on April 3rd. Please use subject line "15-451 MINI #4" so that the email is properly routed to your TA and follow the other instructions for submission.
• 04/24: Mini 5 is available, and due by midnight on May 1st. Please use subject line "15-451 MINI #5" so that the email is properly routed to your TA and follow the other instructions for submission.

Homeworks

• 01/23: pdf ps Homework 1 is now available and due January 30th in class.
For question 1, you can assume T(x) = 1 on part (a) for x <=4, on part (b) for x <= 3, and on part (c) for x <=5 solns pdf solns ps
• 01/23: pdf ps Homework 2 is now available. Please sign up by Sunday, 11:59 pm for a presentation slot. After you receive an email confirmation from Michelle, meet your grader at their office at your confirmed time.
solns pdf solns ps
• 01/23: pdf ps Homework 3 is now available and due March 8th in class.
For question 4, linear time means O(|V| + |E|). Assume an adjacency list representation of the graph. For question 1, we are asking you to prove that rotations remain constant time in an augmented BST. solns pdf solns ps
• 03/20: Instructions for signups for HW4 are now available. pdf ps HW4. Solutions now available solns pdf solns ps
• 04/03: pdf ps Homework 5 is now available and due April 10th in class.
Clarification: For question 1, you need to solve the search problem in polynomial time, given a polynomial time algorithm for the decision problem. Exponential time is not acceptable. pdf solutions ps solutions
• 03/20: pdf ps HW 6.

Statistics

Lecture notes

1. 01/16: Intro & Admin. Karatsuba/Strassen. [ The first 10 lectures]
01/17: Recitation notes
2. 01/18: Asymptotic analysis, solving recurrences.
3. 01/23: Probabilistic analysis, Randomized Quicksort.
01/24: Recitation notes
4. 01/25: Linear-time Selection (randomized and deterministic).
5. 01/30: Lower bounds for comparison-based sorting.
01/31: Recitation notes
6. 02/01: Concrete models of computation and tight upper/lower bounds
7. 02/06: Amortized Analysis
02/07: Recitation notes
8. 02/08: Search trees: B trees and treaps
9. 02/13: Digit-based sorting/data-structures (radix sort, tries)
10. 02/15: Universal and Perfect Hashing
11. 02/20: Dynamic Programming [ Lectures 11-18 ]
12. 02/22: Graph Algorithms I
13. 02/27: Graph Algorithms II
02/28: Recitation notes--not all sections reviewed these! Most of section was spent going over a practice test
14. 03/01: Midterm Review
15. 03/06: Midterm. Extra extra credit is now online. Remember that you must show an O(m+n) algorith, or prove that none exists. These will be presented to Manuel orally after break
16. 03/08: Graph Algorithms III
17. 03/20: Network Flows I
18. 03/22: Network Flows II
19. 03/27: Linear Programming [ Lectures 19-26 ]
20. 03/29: NP Completeness I
21. 04/03: NP Completeness II
22. 04/05: NP Completeness and Approximation Algorithms
23. 04/10: Online Algorithms
24. 04/12: Number Theory I
25. 04/17: Number Theory II
26. 04/24: Number Theory III -- Fourier Transforms
27. 04/26: Game Theory [ Lectures 27-29 ]
28. 05/01: Game Theory, continued (we did the minimax proof)
29. 05/03: Cake cutting. Last class!