Future Lectures
The topics for lectures in the future are tentative and subject to change. Also the links for future lectures are from Fall 2018 and Fall 2019. Recordings of Spring 2020 lectures are also available from UBLearns.
| Date | Topic | Notes |
| Mon, Jan 27 | Introduction S20 F19 F18 | (HW 0 out) Week 1 recitation notes |
| Wed, Jan 29 | Main Steps in Algorithm Design S20 F19 F18 | |
| Fri, Jan 31 | Stable Matching Problem S20 F19 F18 | [KT, Sec 1.1] |
| Mon, Feb 3 | Perfect Matchings S20 F19 F18 | [KT, Sec 1.1] (HW 0 in) Week 2 recitation notes |
| Wed, Feb 5 | Stable Matching Problem S20 F19 F18 | [KT, Sec 1.1] |
| Fri, Feb 7 | Gale Shapley algorithm S20 F19 F18 | [KT, Sec 1.1] (HW 1 out) |
| Mon, Feb 10 | Gale Shapley alg. outputs a stable matching S20 F19 F18 | [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 12 | Efficient algorithms and asymptotic analysis S20 F19 F18 | [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 14 | Runtime Analysis of Gale-Shapley algorithm S20 F19 F18 | [KT, Sec 2.3] (HW 2 out) |
| Mon, Feb 17 | Graph Basics S20 F19 F18 | [KT, Sec 2.3, 3.1] ( Week 4 recitation notes |
| Wed, Feb 19 | Computing Connected Component S20 F19 F18 | [KT, Sec 3.2] Reading Assignment: Care package on trees Reading Assignment: BFS by examples |
| Fri, Feb 21 | Explore Algorithm S20 F19 F18 | [KT, Sec 3.2] (HW 3 out) |
| Mon, Feb 24 | Runtime Analysis of BFS algorithm S20 F19 F18 | [KT, Sec 3.3] ( Week 5 recitation notes |
| Wed, Feb 26 | More graph stuff S20 F19 F18 | [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, Feb 28 | Interval Scheduling Problem S20 F19 F18 | [KT, Sec 4.1] (HW 4 out, Video Mini Project Team Composition Due)
|
| Mon, Mar 2 | Greedy Algorithm for Interval Scheduling S20 F19 F18 | [KT, Sec 4.1] ( Reading Assignment: [KT, Sec 4.1, 4.2] Week 6 recitation notes |
| Wed, Mar 4 | Shortest Path Problem S20 F19 F18 | [KT, Sec 4.4] Reading Assignment: Care package on minimizing maximum lateness |
| Fri, Mar 6 | Dijkstra's algorithm S20 F19 F18 | [KT, Sec 4.4] (Quiz 1) |
| Mon, Mar 9 | Proof of Dijkstra's algorithm S20 F19 F18 | [KT, Sec 4.5] (HW 4 in) Reading Assignment: [KT, Sec 4.5] |
| Wed, Mar 11 | Mid-term exam: I | |
| Fri, Mar 13 | Mid-term exam: II | |
| Mon, Mar 16 | No Class | Spring Recess |
| Wed, Mar 18 | No Class | Spring Recess |
| Fri, Mar 20 | No Class | Spring Recess (HW 5 out) |
| Mon, Mar 23 | Minimum Spanning Tree Problem S20 F19 F18 | [KT, Sec 4.5] Week 7 recitation notes and video |
| Wed, Mar 25 | Cut Property Lemma S20 F19 F18 | [KT, Sec 4.5] Reading Assignment: [KT, Sec 4.5, 4.6] |
| Fri, Mar 27 | Mergesort S20 F19 F18 | [KT, Sec 5.1] |
| Mon, Mar 30 | Solving recurrence relations S20 F19 F18 | [KT, Sec 5.2] (HW 5 in) Week 8 recitation notes and video |
| Wed, Apr 1 | Counting Inversions S20 F19 F18 | [KT, Sec 5.3] |
| Fri, Apr 3 | Multiplying large integers S20 F19 F18 | [KT, Sec 5.5] (HW 6 out) Reading Assignment: Unraveling the mystery behind the identity |
| Mon, Apr 6 | Closest Pair of Points S20 F19 F18 | [KT, Sec 5.4] Week 9 recitation notes and video |
| Wed, Apr 8 | Kickass Property Lemma S20 F19 F18 | [KT, Sec 5.4] |
| Fri, Apr 10 | Weighted Interval Scheduling S20 F19 | [KT, Sec 6.1] (HW 7 out, |
| Mon, Apr 13 | Recursive algorithm for weighted interval scheduling problem S20 F19 F17 | [KT, Sec 6.1] ( Week 10 recitation notes and video |
| Wed, Apr 15 | Subset sum problem S20 F19 F18 | [KT, Sec 6.1, 6.2, 6.4] |
| Fri, Apr 17 | Dynamic program for subset sum S20 F19 F18 | [KT, Sec 6.4] (HW 8 out) |
| Mon, Apr 20 | Shortest path problem S20 F19 F18 | [KT, Sec 6.8] ( Week 11 recitation notes and video |
| Wed, Apr 22 | Bellman-Ford algorithm S20 F19 F18 | [KT, Sec 6.8] |
| Fri, Apr 24 | The P vs. NP problem S20 F19 | [KT, Sec 8.1] (HW 9 out, Video Mini Project survey due) |
| Mon, Apr 27 | More on reductions S20 F19 | [KT, Sec 8.1] ( Week 12 recitation notes and video |
| Wed, Apr 29 | The SAT problem S20 F19 | [KT, Sec 8.2] |
| Fri, May 1 | NP-Completeness S20 F19 | [KT, Sec. 8.3, 8.4] (HW 10 out) |
| Mon, May 4 | k-coloring problem S20 F19 | [KT, Sec 8.7] ( Week 13 recitation notes and video |
| Wed, May 6 | k-coloring is NP-complete S20 F19 F18 | [KT, Sec 8.7] |
| Fri, May 8 | Wrapup S20 F19 F18 | |
| Monday, May 11 | Final Exam | (3:30pm-6:30pm take-home exam) |