CMU 15-451    Algorithms    Spring 2004

Instructors: Gary Miller    Danny Sleator

TAs: Shobha Venkataraman   Nina Balcan   Stefan Niculescu

Announcements:

• CORRECT DUE DATE FOR ASSIGNMENT 7: 5pm Friday April 30 in room 7130.
• Final Exam Review Session: Sunday May 2 from 7pm on in room Wean 5409.
• Last Spring's Final Exam (ignore universal hashing and most of problem 8)
• Last Fall's Final Exam (ignore the FFT problem)
• Midterm 2 solutions are here. [pdf, ps]
• Midterm 1 solutions are here. [pdf, ps]
• Stefan's office hours are back to the usual time. 3 to 5pm.

General info

• Here is a schedule and syllabus for the course.
• Here is a link to the course personnel information.
• Here is a link to the blackboard site for this course. 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.
• Here are some recommended texts. We recommend the textbook Introduction to Algorithms by T. Cormen, C. Leiserson, R. Rivest, C. Stein. We'll be supplying lecture notes for the material we present in the class as we go along.
• Here are the grading and other course policies.

Homeworks

• Minis -- These are "mini assignments" given on alternate weeks. They'll be posted on the web site on Friday, and will be due the following Thursday. You'll turn these in before lecture.
• Written Homeworks -- These are longer and more difficult, you'll have to prepare your solutions on paper and turn them in in class.
• Oral Homeworks -- You will present your solutions to a course staff member, as well as turn in a written solution to the problem.

  ---

  Minis

  • Mini 1 [ps, pdf]. Due Before class Thursday Jan 22. Solution [ps, pdf].
  • Mini 2 [ps, pdf]. Due Friday by 5PM in Wean 7130, Jan 30.
  • Mini 3 [ps, pdf], Due Friday Feb 13 by 5PM in Wean 7130 (Make sure include your section letter on it.) Solution [ps, pdf].
  • Mini 4 [ps, pdf], Due Tuesday April 13 at the start of class. (Make sure include your section letter on it.)

  ---

  Homeworks

  • Homework 1 [ps, pdf]. Due Before class Thursday Feb 5. Solution for Problem 2 [ps, pdf].
  • Homework 2 [ps, pdf]. Sign up for Oral before Feb 15. Solutions [ps, pdf].
  • Homework 3 [ps, pdf]. Due Friday by 5pm March 5, in room 7130. Solutions [pdf].
  • Homework 4 [ps, pdf]. Sign up for Oral before Mar 18. This is an oral assignment, although each student must turn in his/her own written solution to all problems, at the time of grading. Please contact glmiller@cs.cmu.edu if you have signup problems. Solutions [ps].
  • Homework 5 [ps, pdf]. Due Tuesday by 5pm April 6, in room 7130. Solutions [pdf].
  • Homework 6 [ps, pdf]. Oral presentations April 19-20. SIGN UP. Solutions [pdf].
  • Homework 7 [ps, pdf]. Due Friday April 30 at 5pm, in room 7130.

Lecture notes

1. 01/13: [ps] Asymptotic analysis, solving recurrences
2. 01/15: [power point] Intro & Admin       Karatsuba/Strassen (notes under lecture 1).
   
3. 01/20: [ps,pdf] Probabilistic Analysis and Randomized Quicksort
4. 01/22: Selection algorithms: deterministic and randomized. (notes under lecture 1)
5. 01/26: [pdf] Radix sort, lexicographic sort.
   
6. 01/28: Sorting Lower Bounds. See chapter 5 of the notes for lecture 1.
7. 02/03: [pdf] Dynamic Programming from CLRS.
   
8. 02/05: [pdf] Optimal Binary Search Trees.
   
9. 02/10: [txt] Binary Search Trees       [txt] Random Binary Search Trees (Treaps)
10. 02/12: [pdf,ps] Amortized Analysis       [txt] Growing and Shrinking a Table
11. 02/12: [txt] Splay Trees       Demo of Top-Down Splaying
12. 02/19: [pdf] Minimum Spanning Trees from CLRS.
    
13. 02/24: [pdf] Depth First Search from CLRS.
               [pdf] Bi-Connected-Components from Reingold et. al.
    
14. 02/26: Midterm Exam 1
15. 03/02: [pdf] Shortest Paths from CLRS.
    
16. 03/04: More graph algorithms, see notes from previous lecture.
17. 03/16: [txt] Max-Flow Lecture I.
    
18. 03/18: [txt] Max-Flow Lecture II.
    
19. 03/23: [txt] Computational Geometry.
    
20. 03/25: More computational geometry, see notes from previous lecture.
21. 03/30: [txt] Fibonacci Heaps
22. 04/01: Midterm Exam 2
23. 04/06: [txt] Competitive Algorithms I (Deterministic)
24. 04/08: [txt] Competitive Algorithms II (Paging and Randomized Competitiveness)
25. 04/13: [txt] Linear Programming I            [pdf] Diet Problem
26. 04/20: Linear programming II, see notes from previous lecture.
27. 04/22: [pdf] NP-completeness I
28. 04/27: [pdf] NP-completeness II            [pdf] NP-completeness III
29. 04/29: [txt] Approximation Algorithms