| Date | Topics |
|---|---|
| Tuesday, January 17 | Administrivia, the mathematics of dating, and a few problem models (Chapter 1) |
| Thursday, January 19 | Greedy Algorithms (Sections 4.1 and 4.2) |
| Tuesday, January 24 | Minimum Spanning Trees (Section 4.5)
Homework 0 due, 11:00am (Solutions: pdf, ps) |
| Thursday, January 26 | Data Structures: Priority Queues and Union-Find (Sections 2.5, and 4.6) |
| Tuesday, January 31 | Huffman Codes (Section 4.8)
Homework 1 due, 11:00am Headbanging 1 |
| Thursday, February 2 | Divide and Conquer: Sorting and Recurrences (Sections 5.1 and 5.2) |
| Tuesday, February 7 | Closest Pair and Multiplication
(Sections 5.4 and 5.5)
Homework 2 due, 11:00am Headbanging 2 |
| Thursday, February 9 | Fast Fourier Transforms (Section 5.6) |
| Tuesday, February 14 | Dynamic Programming: Weighted Interval Scheduling
and Segmented Least Squares (Sections 6.1, 6.2, and 6.3)
Homework 3 due, 11:00am Headbanging 3 |
| Thursday, February 16 | RNA secondary structure and Sequence Alignment (Sections 6.5, 6.6, and 6.7) |
| Tuesday, February, 21 | Midterm I
Headbanging 4 |
| Thursday, February 23 | All pairs shortest path and Knapsack (Section 6.4, 6.8, 6.9, and 6.10) |
| Tuesday, February 28 | Basic Network Flow Algorithms
(Section 7.1, 7.2 and 7.3)
Homework 4 due, 11:00am Headbanging 5 |
| Thursday, March 2 | Continuation of Network Flow (see previous lecture) |
| Tuesday, March 7 | Discussion of Midterm I results and solutions
Homework 5 due, 11:00am Headbanging 6 |
| Thursday, March 9 | Network Flow Applications and Extensions (Section 7.5, 7.6, 7.7, and 7.8) |
| Tuesday, March 14 | More Network Flow Applications
(Section 7.10, 7.11, and 7.12)
Homework 6 due, 11:00am Headbanging 7 |
| Thursday, March 16 | Linear Programming (Book on Linear Programming by Vanderbei) |
| March 21 and March 23 | Spring Break |
| Tuesday, March 28 | In class review session for midterm |
| Thursday, March 30 | Midterm II |
| Tuesday, April 4 | Polynomial Time Reductions
(Section 8.1 and 8.2)
Headbanging 8 |
| Thursday, April 6 | NP-Completeness and Cook-Levin Theorem (Section 8.3 and 8.4) |
| Tuesday, April 11 | NP Completeness (Section 8.5 and 8.7)
Homework 7 due, 11:00am Headbanging 9 |
| Thursday, April 13 | co-NP, NP and P, and Approximation Algorithms (Section 8.9 and 11.1) |
| Tuesday, April 18 | Set Cover (Section 11.3)
Homework 8 due, 11:00am Headbanging 10 |
| Thursday, April 20 | Vertex Cover: Pricing Method, Primal-Dual Method, LP rounding, and polynomial-time approximation schemes (Section 11.6 and 11.8) |
| Tuesday, April 25 | Randomization (Chapter 13)
Kevin Wayne's lecture slides (PPT,
PDF)
Headbanging 11 |
| Thursday, April 27 | Randomization (Chapter 13) Kevin Wayne's lecture slides (PPT, PDF) |
| Tuesday, May 2 | Randomization (Chapter 13) Kevin Wayne's lecture slides (PPT, PDF) |