| Date | Topics |
|---|---|
| Tuesday, January 16 | Administrivia, the mathematics of dating, and a few model problem (Chapter 1) |
| Thursday, January 18 | Introduction to Greedy Algorithms (Sections 4.1 and 4.2) |
| Tuesday, January 23 | Minimum Spanning Trees (Section 4.5)
Homework 0 due, 10:00pm (Solutions: pdf) |
| Thursday, January 25 | Data Structures: Priority Queues and Union-Find (Sections 2.5, and 4.6) |
| Tuesday, January 30 | Huffman Codes (Section 4.8)
Homework 1 due, 10:00pm |
| Thursday, February 1 | Divide and Conquer: Sorting and Recurrences (Sections 5.1 and 5.2) |
| Tuesday, February 6 | Closest Pair and Multiplication
(Sections 5.4 and 5.5)
Homework 2 due, 10:00pm |
| Thursday, February 8 | Fast Fourier Transforms (Section 5.6) |
| Tuesday, February 13 | No classes; enjoy the shovelling. |
| Thursday, February 15 | Dynamic Programming: Weighted Interval
Scheduling and Segmented Least Squares (Sections 6.1, 6.2, and 6.3)
Homework 3 due, 12:00pm |
| Tuesday, February, 20 | Midterm I (on Chapters 1 through 5; Greedy and Divide and Conquer paradigms) |
| Thursday, February 22 | RNA secondary structure and Sequence Alignment (Sections 6.5, 6.6, and 6.7) |
| Tuesday, February 27 | All pairs shortest path and Knapsack
(Section 6.4, 6.8, 6.9, and 6.10)
Homework 4 due, 10:00pm |
| Thursday, March 1 | Basic Network Flow Algorithms (Section 7.1, 7.2 and 7.3) |
| Tuesday, March 6 | Continuation of Network Flow
Homework 5 due, 10:00pm |
| Thursday, March 8 | Applications of Network Flow
|
| Tuesday, March 13 | Continuation of Applications of Network Flow
Homework 6 due, 10:00pm |
| March 20 and March 22 | Spring Break |
| Tuesday, March 27 | Linear Programming
(Book
on Linear Programming by Vanderbei)
8-9pm: Review session for midterm 2 (1404 SC) |
| Thursday, March 29 | Midterm II (Chapters 6 and 7; Dynamic Programming and Network Flows) |
| Tuesday, April 3 | Polynomial Time Reductions (Section 8.1 and 8.2) |
| Thursday, April 5 | NP-Completeness and Cook-Levin Theorem (Section 8.3 and 8.4) |
| Tuesday, April 10 | NP Completeness (Section 8.5 and 8.7)
Homework 7 due, 10:00pm |
| Thursday, April 12 | co-NP, NP and P, and Approximation Algorithms (Section 8.9 and 11.1) |
| Tuesday, April 17 | Set Cover (Section 11.3) |
| Thursday, April 19 | Vertex Cover: Pricing Method, Primal-Dual Method, LP rounding, and polynomial-time approximation schemes (Section 11.6 and 11.8) |
| Tuesday, April 24 | Randomization (Chapter 13) MAX-3SAT, Global Mincut |
| Thursday, April 26 | Randomization (Chapter 13) Monte Carlo vs. Las Vegas, 2-SAT, Majority, Bucket-sort |
| Tuesday, May 1 | Hashing (Chapter 13.6) |