- (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.

- 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.

- 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

- 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 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)

- 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
[ps,pdf]
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)]
[Strong Components
(pdf)]

- 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 [pdf]
- 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)