CMU       15-451       Spring 2006

Instructor: Danny Sleator

TAs: Daniel Golovin, Lea Kissner

Announcements

Hot off the press:

• (5/4) Solutions to HW7 have been posted.
  (To clarify #3(c) a bit, "the distance between u and v under x" is the length of the shortest u to v path, where edge e has length x(e)).
• (5/3) The final exam will take place on Monday May 8 at 8:30am in Scaife Hall 125. You may bring one page of notes.
• Previous Final Exams: Fall 2005, Spring 2004
• (5/2) Solutions for HW5 have been posted.
• (4/26) Solutions for HW6 have been posted.
• (4/25) HW7 is out. We strongly suggest you start soon, and you will probably find the assignment much easier if you read chapter 8 the textbook. If you are short on time, Daniel recommends you carefully read from the intro to chapter 8 up to 8.4 (inclusive), and skim the rest of the chapter. Make sure to look at 8.10.

Older stuff:

• Midterms from previous semesters (PS format): one, two.
• (2/23) Additional notes on splay trees have been posted. This new material is optional reading, but we recommend you take a look.
• (2/10) If you did not pick up your graded homeworks in section, you can get them from Nicole Stenger, Wean 4116.

General info

• Lectures: Tue/Thu 12-1:20, Hammerschlag Hall B103.
• Recitations: Wed 11:30/12:30. (A in PH 226B; B in PH 225B).
• Course information
• Schedule
• Blackboard Site. The blackboard system will be used only for discussion groups and maintaining a grade book. This page (the one you're looking at) is the primary web site for this course.
• Writing up assignments with LaTeX

Minis

• Mini 1. Due midnight January 24. Solutions
• Mini 2. Due by email at 11:59pm February 7th. Solutions
• Mini 3 cancelled.
• Mini 4. Due by email at 11:59pm Tuesday March 7.
• Mini 5. Due by email at 11:59pm Tuesday March 28.

Homeworks

• Homeworks must be either handwritten very neatly, or typed up. Acceptable formats are PDF and PS. Microsoft DOC format will not be accepted, since equations tend to display incorrectly between different versions of Word. A popular (among computer scientists and mathematicians) option for typesetting text is LaTeX, which you may want to check out.
• When you turn in solutions, you must supply a proof with your answers.

• Homework 1 [ps, pdf]. Due (start of class) Jan 31. Solution 1 (PDF).
• Homework 2 [pdf] Sign up here for a presentation slot before February 13th. Solution 2 (PDF).
• Homework 3 [ps, pdf]. Due (start of class) Feb 28. Solution 3 (PDF)
• Homework 4 [ps, pdf]. Oral presentations on March 23rd and 24th. Sign up here (old link) Solution 4
• Homework 5 [ps, pdf]. Due (start of class) Apr 6. Solution 5 (PDF)
• Homework 6 [ps, pdf]. Oral presentations April 17th and 18th. Sign up here. Solution 6
• Homework 7 [ps, pdf]. Due (start of class) May 4. Solution 7 (PDF)

Lecture notes

1. 01/17:Intro & Admin. Karatsuba/Strassen. [ps,pdf]
   
2. 01/19: Asymptotic analysis, solving recurrences (See notes of 01/17).
   
3. 01/24: Probabilistic Analysis, Quicksort (See notes of 01/17).
   
4. 01/26: Selection (See notes of 01/17).
   
5. 01/31: Soring Lower Bounds (See notes of 01/17).
   
6. 02/02: Red-Black Trees [txt].
   
7. 02/07: Amortized Analysis [ps,pdf]   Growing and Shrinking a Table [txt].
   
8. 02/09: Splay Trees [txt].   Advanced Splay Tree Analysis [txt].
9. 02/14: Radix Structures [pdf].   The World's Fastest Scrabble Program [pdf].
   
10. 02/16: Hashing (see 13.6 of the book)
    
11. 02/21: Dynamic Programming (chapter 6 of the book)
    
12. 02/23: Dynamic Programming contd (chapter 6 of the book)
    
13. 02/28: Bellman Ford shortest path algorithm (6.8 and 6.10)
    
14. 03/02: Depth First Search and Strong Components [DFS Background (txt)] [Strong Components (pdf)]
    
15. 03/07: BFS, Dijkstra, Minimum Spanning Trees [txt]
16. 03/09: Midterm Exam (Here it is: [ps])
17. 03/21: Network Flows and Matchings I (7.1-7.3 and 7.5-7.6)
18. 03/23: Network Flows and Matchings I (7.7-7.11)
19. 03/28: Two Algorithms for Finding Closest Pairs (13.7 and 5.4)
20. 03/30: Voronoi Diagrams, Point Location, and Persistence [pdf]
21. 04/04: FFT (5.6)
22. 04/06: Competitive Algorithms (deterministic) [txt]    Migration Problems [pdf]
23. 04/11: Competitive Algorithms (randomized) [txt]
24. 04/13: Linear Programming [txt]
25. 04/18: random problems
26. 04/25: NP-completeness I [pdf]
27. 04/27: NP-completeness II [pdf]
28. 05/02: Approximation Algorithms I (chapter 11.1 and [txt])
29. 05/04: Approximation Algorithms II (chapter 13.4)