CMU 15-451 Spring 2006
TAs: Daniel Golovin, Lea Kissner
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,
- (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.
- Midterms from previous semesters (PS format): one,
- (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.
- 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
- 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
- Writing up assignments with LaTeX
- Mini 1. Due midnight January 24.
- Mini 2. Due by email at 11:59pm February 7th.
- 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 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
- When you turn in solutions, you must supply a proof with your answers.
- 01/17:Intro & Admin. Karatsuba/Strassen. [ps,pdf]
- 01/19: Asymptotic analysis, solving recurrences (See notes of 01/17).
- 01/24: Probabilistic Analysis, Quicksort (See notes of 01/17).
- 01/26: Selection (See notes of 01/17).
- 01/31: Soring Lower Bounds (See notes of 01/17).
- 02/02: Red-Black Trees [txt].
- 02/07: Amortized Analysis
Growing and Shrinking a Table [txt].
- 02/09: Splay Trees [txt].
Advanced Splay Tree Analysis [txt].
- 02/14: Radix Structures [pdf].
The World's Fastest Scrabble Program [pdf].
- 02/16: Hashing (see 13.6 of the book)
- 02/21: Dynamic Programming (chapter 6 of the book)
- 02/23: Dynamic Programming contd (chapter 6 of the book)
- 02/28: Bellman Ford shortest path algorithm (6.8 and 6.10)
- 03/02: Depth First Search and Strong Components
[DFS Background (txt)]
- 03/07: BFS, Dijkstra, Minimum
Spanning Trees [txt]
- 03/09: Midterm Exam (Here it is: [ps])
- 03/21: Network Flows and Matchings I (7.1-7.3 and 7.5-7.6)
- 03/23: Network Flows and Matchings I (7.7-7.11)
- 03/28: Two Algorithms for Finding Closest Pairs (13.7 and 5.4)
- 03/30: Voronoi Diagrams, Point Location, and Persistence
- 04/04: FFT (5.6)
- 04/06: Competitive Algorithms (deterministic) [txt]
Migration Problems [pdf]
- 04/11: Competitive Algorithms (randomized) [txt]
- 04/13: Linear Programming [txt]
- 04/18: random problems
- 04/25: NP-completeness I [pdf]
- 04/27: NP-completeness II [pdf]
- 05/02: Approximation Algorithms I (chapter 11.1 and [txt])
- 05/04: Approximation Algorithms II (chapter 13.4)