Instructor:
Sofya Raskhodnikova
Office hours: Wednesdays, 3pm-5pm, IST 343F
| Date | Syllabus | Reading | Handouts/Homework | |
|---|---|---|---|---|
| Wed, Aug 24 | Introduction, stable matching (slides) | KT, Chap. 1 | General Information, Collaboration Policy | |
| Fri, Aug 26 | Stable matching analysis, asymptotic growth (slides) | KT, Chap. 2 | Homework 1 out (pdf) | |
| Mon, Aug 29 | Graphs (slides) | KT, Chap. 3 | ||
| Wed, Aug 31 | Greedy algorithms: scheduling problems (slides, demo of interval scheduling algorithm) | KT, Chap. 3.1-3.2 | ||
| Fri, Sep 2 | Review of DFS. Greedy algorithms for graph problems: shortest paths and MST (slides) | KT, Chap. 4.4-4.5 | Homework 1 due, homework 2 out (pdf) | |
| Mon, Sep 5 | Labor day -- no lecture. | |||
| Wed, Sep 7 | Greedy algorithms: MST and Huffman codes (slides) | KT, Chap. 4.5-4.8, Erickson's chapter on greedy | ||
| Fri, Sep 9 | 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 | Homework 2 due, homework 3 out (pdf) | |
| Mon, Sep 12 | Divide and conquer: integer and matrix multiplication, closest pair (slides) | KT, Chap. 5.4-5.5, CLRS | ||
| Wed, Sep. 14 | No lecture. | |||
| Fri, Sep 16 | Dynamic programming: Fibonacci numbers, weighted interval scheduling, longest common subsequence (slides) | KT, Chap. 6.1-6.2, 6.6-6.7; Erickson's book | Homework 3 due, homework 4 out (pdf) | |
| Mon, Sep 19 | Dynamic programming: segmented least squares, Knapsack problem (slides) | KT, Chap. 6.3-6.4 | ||
| Wed, Sep 21 | Review. Dynamic programming: weighted independent set (exercise), RNA Secondary Structure (slides for this and the following lecture) | KT, Chap. 6.5, 6.8-6.10 | ||
| Fri, Sep. 23 | No lecture. | Homework 4 due | ||
| Mon, Sep 26 | Shortest Paths: Bellman-Ford. Review. (See slides posted on Sep 21.) | KT, Chap. 6.8-6.10 | Exam 1 Announcement and practice exam (on Angel) | |
| Wed, Sep. 28 | Review. Started FFT (slides on FFT) | KT, Chap. 5.6 | ||
| Wed, Sep. 28 | Midterm 1, 08:15-10:15pm, 012 Walker | |||
| Mon, Oct. 3 | Finish FFT (see slides posted on Sep. 28). Start Network Flow | KT, Chap. 7.1-7.2 | Homework 5 out (pdf) | |
| Wed, Oct. 5 | Network Flow (slides, demo of Ford-Fulkerson) | KT, Chap. 7.1-7.3 | ||
| Fri, Oct. 7 | No lecture | Homework 5 due, homework 6 out (pdf) | ||
| Mon, Oct. 10 | Applications of flow: bipartite matching and disjoint paths (slides) | KT, Chap. 7.5-7.6 | ||
| Wed, Oct. 12 | No lecture | |||
| Fri, Oct. 14 | No lecture | Homework 6 due, homework 7 out (pdf) | ||
| Mon, Oct. 17 | Applications and extensions of flow (slides) | KT, Chap. 7.7-7.11 | ||
| Wed, Oct. 19 | Finish flow (see slides posted on Oct. 17), max-weight bipartite matching | KT, Chap. 7.3,7.8,7.12, Erickson's chapter on max-weight matching | ||
| Fri, Oct. 21 | No lecture | Homework 7 due, homework 8 out (pdf) | ||
| Week of Oct. 24 to Oct. 28 | No lectures | |||
| Fri, Oct. 28 | No lecture | Homework 8 due | ||
| Mon, Oct. 31 | Max-wight bipartite matching | Erickson's chapter on max-weight matching | ||
| Wed, Nov. 2 | Review. Come prepared with questions. | |||
| Wed, Nov. 2 | Midterm 2, 08:15-10:15pm, 012 Walker | |||
| Mon, Nov. 7 | Linear programming: examples (politics, max flow, min cut, min-cost flow, multicommodity flow), forms (general, canonical, slack) | Erickson's chapter on linear programming, CLRS Chap. 29.1-29.2 (according to 2nd edition) | Homework 9: Problems 3 and 7 from Erickson's chapter on LP | |
| Wed, Nov. 9 | Linear programming: duality, geometric view | |||
| Fri, Nov. 11 | No lecture | Homework 9 due | ||
| Mon, Nov. 14 | Computational intractability: poly-time reductions (slides) | KT, Chap. 8.1-8.2 | Homework 10 out (pdf) | |
| Wed, Nov. 16 | Classes P, NP and EXP; NP-completeness (slides) | KT, Chap. 8.3-8.4 | ||
| Fri, Nov. 18 | No lecture | Homework 10 due, homework 11 out (pdf, updated on 11/28) | ||
| Week of Nov. 21 to Nov. 25 | Thanksgiving break: no lectures | |||
| Mon, Nov. 28 | 3D-Matching (slides) | KT, Chap. 8.5-8.10 | ||
| Wed, Nov. 30 | Algorithms for NP-complete problems: solving special cases; approximation algorihtms (slides) | KT, Chap. 10 | ||
| Fri, Dec. 2 | No lecture | Homework 11 due, homework 12: 1) KT, Chap. 10, #2; 2) KT, Chap. 11, #10 | ||
| Mon, Dec. 5 | Approximation algorithms (slides, demo of list scheduling) | KT, Chap. 11 | ||
| Wed, Dec. 7 | Randomized algorithms. Sublinear-time algorithms. (slides) | KT, Chap. 13 | ||
| Fri, Dec. 9 | No lecture | Homework 12 due | ||
| Mon, Dec. 12 | Final exam, 11am-1pm in 333 IST | |||