Future Lectures
The topics for lectures in the future are tentative and subject to change.
| Date | Topic | Notes |
| Mon, Aug 28 | Introduction | (HW 0 out) Week 1 recitation ones |
| Wed, Aug 30 | Main Steps in Algorithm Design | (HW 0 out) |
| Fri, Sep 1 | Stable Matching Problem | [KT, Sec 1.1] (HW 0 in) |
| Mon, Sep 4 | No Class | Labor Day Week 2 recitation notes |
| Wed, Sep 6 | Gale Shapley algorithm | [KT, Sec 1.1] |
| Fri, Sep 8 | Correctness of Gale Shapley algorithms | [KT, Sec 1.1] (HW 1 out) Reading Assignment: Support pages on progress measure and pigeon-hole principle |
| Mon, Sep 11 | Gale Shalpey algorithm outputs a stable matching | [KT, Sec 1.1] Career Services Presentations slides Week 3 recitation notes |
| Wed, Sep 13 | Asymptotic Analysis | [KT, Sec 2.1, 2.2] Reading Assignment: All of [KT, Sec 1.1, 1.2, 2.1, 2.2, 2.4] |
| Fri, Sep 15 | Analysing runtime of an algorithm | [KT, Sec 2.3] (HW 2 out, HW 1 in) Reading Assignment: Worst-case runtime analysis notes |
| Mon, Sep 18 | Runtime analysis of Gale-Shapley algorithm | [KT, Sec 2.3] Reading Assignment: All of [KT, Chap 2] Week 4 recitation notes |
| Wed, Sep 20 | Graph Basics | [KT, Sec 3.1] |
| Fri, Sep 22 | Trees | [KT, Sec 3.1] (HW 3 out, HW 2 in) |
| Mon, Sep 25 | Computing Connected Component | [KT, Sec 3.2] (Mini Project Team Composition Due) Week 5 recitaiton notes |
| Wed, Sep 27 | Graph Representation | [KT, Sec 3.2] |
| Fri, Sep 29 | Runtime Analysis of BFS and DFS | [KT, Sec 3.3] (HW 4 out, HW 3 in) Reading Assignment: [KT, Sec 3.3, 3.4, 3.5] |
| Mon, Oct 2 | Topological Ordering | [KT, Sec 3.6] Week 6 recitation notes |
| Wed, Oct 4 | Analysis of TopOrd algorithm | [KT, Sec 3.6] (Mini Project Pitch Due) |
| Fri, Oct 6 | Interval Scheduling | [KT, Sec 4.1] (HW 5 out, HW 4 in) |
| Mon, Oct 9 | Greedy algorithm for interval scheduling | [KT, Sec 4.1] (Quiz 1) Week 7 recitation notes |
| Wed, Oct 11 | Scheduling to minimize maximum lateness | [KT, Sec 4.2] |
| Fri, Oct 13 | Greedy scheduling algorithm | [KT, Sec 4.2] ( HW 5 in) |
| Mon, Oct 16 | Mid-term exam: I | |
| Wed, Oct 18 | Mid-term exam: II | |
| Fri, Oct 20 | Exchange argument | [KT, Sec 4.2] |
| Mon, Oct 23 | Shortest path problem | [KT, Sec 4.4] Week 8 recitation notes |
| Wed, Oct 25 | Dijkstra's algorithm | [KT, Sec 4.4] |
| Fri, Oct 27 | Minimum Spanning Tree | [KT, Sec 4.5] (HW 6 out) |
| Mon, Oct 30 | Cut Property Lemma | [KT, Sec 4.5] Week 9 recitation notes |
| Wed, Nov 1 | Mergesort | [KT, Sec 5.1] Reading Assignment : [KT, Sec 4.5, 4.6] |
| Fri, Nov 3 | Analysis of Mergesort | [KT, Sec 5.1] (HW 7 out, HW 6 in) |
| Mon, Nov 6 | Integer Multiplication | [KT, Sec 5.5] Week 10 recitation notes |
| Wed, Nov 8 | Counting inversions | [KT, Sec 5.3] |
| Fri, Nov 10 | Closest pair of points | [KT, Sec 5.4] (HW 8 out, HW 7 in) |
| Mon, Nov 13 | Kickass Property Lemma | [KT, Sec 5.4] (Mini Project video due) Week 11 recitation notes |
| Wed, Nov 15 | Weighted Interval Scheduling | [KT, Sec 6.1] |
| Fri, Nov 17 | Dynamic program for weighted interval scheduling | [KT, Sec 6.1, 6.2] (HW 9 out, HW 8 in) |
| Mon, Nov 20 | Subset sum problem | [KT, Sec 6.4] Week 12 recitation notes |
| Wed, Nov 22 | No class | Fall Recess |
| Fri, Nov 24 | No class | Fall Recess |
| Mon, Nov 27 | Dynamic program for subset sum | [KT, Sec 6.4] Week 13 recitation notes |
| Wed, Nov 29 | Shortest path problem | [KT, Sec 6.8] |
| Fri, Dec 1 | Bellman-Ford algorithm | [KT, Sec 6.8] (HW 10 out, HW 9 in) |
| Mon, Dec 4 | NP-completeness | (Quiz 2) Week 14 recitation notes |
| Wed, Dec 6 | Wrapup | |
| Fri, Dec 8 | Presentations | (HW 10 in) |
| Fri, Dec 15 | Final Exam | (noon-2:30pm in NSC 225) |