| Date | Syllabus | Reading (reading in advance in bold) | Handouts/Homework
|
|---|
| Mon, Aug 22 | Introduction, stable matching (slides) | KT,
Chap. 1 | General Information,
Collaboration Policy |
| Wed, Aug 24 | Stable matching analysis, asymptotic
growth (slides) |
KT, Chap. 2 (2.1,2.2,2.4) | Homework 1 out (pdf) |
| Mon, Aug 29 | Data structures. Graph traversals. (slides) | KT,
Chap. 3 |
|
| Wed, Aug 31 | DFS and applications (slides) | KT, Chap. 3 (also CLRS 22.3) | Homework 2 out (pdf) |
| Mon, Sep 5 | Labor day -- no lecture. |
| Wed, Sep 7 | Topological sort, strongly connected components (slides) | KT, Chap. 3 (also CLRS 22.3-22.5) | Homework 3 out (pdf)
|
| Mon, Sep 12 | Greedy algorithms: scheduling problems (slides, demo of interval scheduling algorithm) | KT, Chap. 2.5, 4.1-4.3 |
|
| Wed, Sep 14 | Greedy algorithms for graph problems: shortest paths and MST
(slides),
Erickson's chapter on shortest paths | KT, Chap. 4.4-4.5 | Homework 4 out (pdf)
|
| Mon, Sep 19 | Greedy algorithms: MST, max-spacing clustering, and Huffman codes (slides) | KT, Chap. 4.5-4.8 |
|
| Wed, Sep 21 | Divide and conquer: merge sort, counting inversions, binary search, exponentiation. Solving recurrences: recursion tree method,
Master theorem, (optional) Akra-Bazzi method (slides, demos of merge and merge&count) | KT, Chap. 5.1-5.3 |
|
| Mon, Sep 26 | Divide and conquer: closest pair, integer and matrix multiplication, median and order statistics (slides) | KT, Chap. 5.4-5.5, CLRS |
|
| Wed, Sep. 28 | Review |
| Homework 5 out (pdf)
|
| Wed, Sep. 28 | Midterm 1,
08:15-10:15pm, 073 Willard |
| Mon, Oct. 3 | Dynamic programming: Fibonacci numbers, weighted interval scheduling, longest common subsequence (slides) |
KT, Chap. 6.1-6.2, 6.6-6.7; Erickson's book |
|
| Wed, Oct. 5 | Dynamic programming: segmented least squares, Knapsack problem (slides) | KT, Chap. 6.3-6.4 | Homework 6 out (pdf)
|
| Mon, Oct. 10 | Guest lecture by Piotr Berman on FFT (slides on FFT)
| KT, Chap. 5.6 |
|
| Wed, Oct 12 | Dynamic programming: RNA Secondary Structure, Bellman-Ford (slides) | KT, Chap. 6.5, 6.8-6.9 | Homework 7 out (pdf)
|
| Mon, Oct. 17 | Finish Bellman-Ford, detecting negative-weight cycles, network flow (slides) | KT, Chap. 7.1-7.3 |
|
| Wed, Oct. 19 | Peer-grading exercise, Max-Flow Min-Cut Theorem, Ford-Fulkerson (slides, demo of Ford-Fulkerson) | KT, Chap. 7.1-7.3 | Homework 8 out (pdf)
|
| Mon, Oct. 24 | Max-Flow algorithms, applications: max bipartite matching (slides) | KT, Chap. 7.5-7.6 | |
|
| Wed, Oct. 26 | Applications of flow: bipartite matching and disjoint paths (slides) | KT, Chap. 7.5-7.6 | |
|
| Mon, Oct. 31 | Applications and extensions of flow (slides) | KT, Chap. 7.7-7.11 |
|
| Wed, Nov. 2 | Review. Come prepared with questions. | | Homework 9 out (pdf)
|
| Wed, Nov. 2 | Midterm 2,
08:15-10:15pm, 073 Willard |
| Mon, Nov. 7 | Lecture by Nithin Varma (slides)
| |
|
| Wed, Nov. 9 | Review flow. Linear programming: examples, forms (general, canonical, slack) (slides)
| Erickson's chapter on linear programming
| Homework 10 out (pdf)
|
| Mon, Nov. 14 | Linear programming: more examples, started duality (slides), exam 2 is returned
| |
|
| Wed, Nov. 16 | Linear programming: duality (slides) | | Homework 11 out (pdf)
|
|
| Week of Nov. 21 to Nov. 25 | Thanksgiving break: no lectures
|
| Mon, Nov. 28 | Computational intractability: poly-time reductions (slides) | KT, Chap. 8.1-8.2 |
|
| Wed, Nov. 30 | Classes P, NP and EXP; NP-completeness (slides) | KT, Chap. 8.3-8.4 | Homework 12 out (pdf)
|
| Mon, Dec. 5 | 3D-Matching, coping with NP-completness (slides) | KT, Chap. 8.5-8.10, Chap. 10.1 |
|
| Wed, Dec. 7 | Approximation algorithms (slides, demo of list scheduling) | KT, Chap. 11 |
|
| Mon, Dec. 12 | Final exam, 8:00 AM - 9:50 AM, 067 Willard Bldg |