Future Lectures
The topics for lectures in the future are tentative and subject to change. Also the links for future lectures are from Spring 2020 and Fall 2019.
| Date | Topic | Notes |
| Mon, Feb 1 | Introduction S21 S20 F19 | HW 0 out Week 1 recitation notes |
| Wed, Feb 3 | Main Steps in Algorithm Design S21 S20 F19 | |
| Fri, Feb 5 | Stable Matching Problem S21 S20 F19 | [KT, Sec 1.1] |
| Mon, Feb 8 | Perfect Matchings S21 S20 F19 | HW 0 due [KT, Sec 1.1] Week 2 recitation notes |
| Wed, Feb 10 | Stable Matching Problem S21 S20 F19 | [KT, Sec 1.1] |
| Fri, Feb 12 | Gale Shapley algorithm S21 S20 F19 | HW 1 out [KT, Sec 1.1] |
| Mon, Feb 15 | Gale Shapley alg. outputs a stable matching S21 S20 F19 | [KT, Sec 1.1]
Reading Assignment: Pigeonhole principle Reading Assignment: Asymptotic notation care package Reading Assignment: Using a Progress Measure Week 3 recitation notes |
| Wed, Feb 17 | Efficient algorithms and asymptotic analysis S21 S20 F19 | [KT, Sec 1.1]
Reading Assignment: Worst-case runtime analysis notes Reading Assignment: [KT, Sec 1.1, 2.1, 2.2, 2.4] |
| Fri, Feb 19 | Runtime Analysis of Gale-Shapley algorithm S21 S20 F19 | HW 1 due HW 2 out [KT, Sec 2.3] |
| Mon, Feb 22 | Graph Basics S21 S20 F19 | [KT, Sec 2.3, 3.1]
Week 4 recitation notes |
| Wed, Feb 24 | Computing Connected Component S21 S20 F19 | [KT, Sec 3.2]
Reading Assignment: Care package on trees Reading Assignment: BFS by examples |
| Fri, Feb 26 | Explore Algorithm S21 S20 F19 | HW 2 due [KT, Sec 3.2] |
| Mon, Mar 1 | Runtime Analysis of BFS algorithm S21 S20 F19 | [KT, Sec 3.3] Week 5 recitation notes |
| Wed, Mar 3 | More graph stuff S21 S20 F19 | [KT, Sec 3.3, 3.6] Reading Assignment: [KT, Sec 3.3, 3.4, 3.5, 3.6] Reading Assignment: Care package on topological ordering |
| Fri, Mar 5 | Interval Scheduling Problem S21 S20 F19 | HW 3 out Video Project Team Composition and Case Study Due [KT, Sec 4.1] |
| Mon, Mar 8 | Greedy Algorithm for Interval Scheduling S21 S20 F19 | [KT, Sec 4.1] Reading Assignment: [KT, Sec 4.1, 4.2] Week 6 recitation notes |
| Wed, Mar 10 | Shortest Path Problem S21 S20 F19 | [KT, Sec 4.4] Reading Assignment: Care package on minimizing maximum lateness |
| Fri, Mar 12 | Dijkstra's algorithm S21 S20 F19 | Quiz 1 HW 3 due [KT, Sec 4.4] |
| Mon, Mar 15 | Proof of Dijkstra's algorithm S21 S20 F19 | [KT, Sec 4.5]
Reading Assignment: [KT, Sec 4.5] |
| Wed, Mar 17 | Mid-term exam: I | |
| Fri, Mar 19 | Mid-term exam: II |
HW 4 out |
| Mon, Mar 22 | Minimum Spanning Tree Problem S21 S20 F19 | [KT, Sec 4.5] Week 7 recitation notes |
| Wed, Mar 24 | Cut Property Lemma S21 S20 F19 | [KT, Sec 4.5] Reading Assignment: [KT, Sec 4.5, 4.6] |
| Fri, Mar 26 | Mergesort S21 S20 F19 | HW 4 due [KT, Sec 5.1] |
| Mon, Mar 29 | Solving recurrence relations S21 S20 F19 | [KT, Sec 5.2] Week 8 recitation notes |
| Wed, Mar 31 | Counting Inversions S21 S20 F19 | [KT, Sec 5.3] |
| Fri, Apr 2 | Multiplying large integers S21 S20 F19 | HW 5 out [KT, Sec 5.5] Reading Assignment: Unraveling the mystery behind the identity |
| Mon, Apr 5 | Closest Pair of Points S21 S20 F19 | [KT, Sec 5.4] Week 9 recitation notes |
| Wed, Apr 7 | Kickass Property Lemma S21 S20 F19 | [KT, Sec 5.4] |
| Fri, Apr 9 | Weighted Interval Scheduling S21 S20 F19 | HW 5 due HW 6 out [KT, Sec 6.1] |
| Mon, Apr 12 | Recursive algorithm for weighted interval scheduling problem S21 S20 F19 | [KT, Sec 6.1] Week 10 recitation notes |
| Wed, Apr 14 | Iterative algorithm for weighted interval scheduling problem S21 S20 F19 | Video Project Submission Due [KT, Sec 6.1, 6.2, 6.4] |
| Fri, Apr 16 | Subset sum problem S21 S20 F19 | HW 6 due [KT, Sec 6.4] |
| Mon, Apr 19 | Shortest path problem S21 S20 F19 | [KT, Sec 6.8] Week 11 recitation notes |
| Wed, Apr 21 | Bellman-Ford algorithm S21 S20 F19 | Video Project Survey Due [KT, Sec 6.8] |
| Fri, Apr 23 | No lecture! | HW 7 out [KT, Sec 8.1] |
| Mon, Apr 26 | The P vs. NP problem S21 S20 F19 | [KT, Sec 8.1] Week 12 recitation notes |
| Wed, Apr 28 | More reductions S21 S20 F19 | [KT, Sec 8.2] |
| Fri, Apr 30 | The SAT problem S21 S20 F19 | HW 7 due HW 8 out [KT, Sec. 8.3, 8.4] |
| Mon, May 3 | NP-Completeness S21 S20 F19 | Quiz 2 [KT, Sec 8.7] Week 13 recitation notes |
| Wed, May 5 | k-coloring problem S21 S20 F19 | [KT, Sec 8.7] |
| Fri, May 7 | Wrap-up S21 S20 F19 | HW 8 due |
| Wednesday, May 12 | Final Exam | 3:30pm-6:00pm live over Zoom |