CSE 331 Fall 2022 Schedule
Previous schedules: 2022 (Spring) , 2021 (Fall), 2021 (Spring) , 2020 , 2019, 2018, 2017, 2016, 2014 , 2013 , 2012 , 2011 , 2010 and 2009 .
Future Lectures
The topics for lectures in the future are tentative and subject to change. Also the links for future lectures are from Fall 2017, Fall 2018, Fall 2019 and Fall 2021. Recordings of Fall 2022 lectures are also available from UBLearns.
| Date | Topic | Notes |
| Mon, Aug 29 | Introduction F22 F21 F19 F18 F17 | |
| Tue, Aug 30 | (HW 0 out) | |
| Wed, Aug 31 | Main Steps in Algorithm Design F22 F21 F19 F18 F17 | Week 1 recitation notes |
| Fri, Sep 2 | Stable Matching Problem F22 F21 F19 F18 F17 | [KT, Sec 1.1] |
| Mon, Sep 5 | No Class | Labor Day |
| Tue, Sep 6 | (HW 0 in) | |
| Wed, Sep 7 | Perfect Matchings F22 F21 F19 F18 F17 | [KT, Sec 1.1]
Week 2 recitation notes |
| Fri, Sep 9 | Algorithms for stable matching problem F22 F21 F19 F18 F17 | [KT, Sec 1.1] |
| Mon, Sep 12 | Gale Shapley algorithm F22 F21 F19 F18 F17 | [KT, Sec 1.1] Reading Assignment: Pigeonhole principle Reading Assignment: Asymptotic notation care package |
| Tue, Sep 13 | (HW 1 out) | |
| Wed, Sep 14 | Gale Shapley algorithm outputs a stable matching F22 F21 F19 F18 F17 | [KT, Sec 1.1] Reading Assignment: Proof details of GS termination Week 3 recitation notes |
| Fri, Sep 16 | Efficient algorithms and asymptotic analysis F22 F21 F19 F18 F17 | [KT, Sec 1.1] Reading Assignment: Worst-case runtime analysis notes Reading Assignment: [KT, Sec 1.1, 2.1, 2.2, 2.4] |
| Mon, Sep 19 | Runtime Analysis of Gale-Shapley algorithm F22 F21 F19 F18 F17 | [KT, Sec 2.3] |
| Tue, Sep 20 | (HW 2 out, HW 1 in) | |
| Wed, Sep 21 | Graph Basics F22 F21 F19 F18 F17 | [KT, Sec 2.3, 3.1]
Week 4 recitation notes |
| Fri, Sep 23 | Computing Connected Component F22 F21 F19 F18 F17 | [KT, Sec 3.2] Reading Assignment: Care package on trees Reading Assignment: BFS by examples |
| Mon, Sep 26 | Explore Algorithm F22 F21 F19 F18 F17 | [KT, Sec 3.2] |
| Tue, Sep 27 | (HW 3 out, HW 2 in) | |
| Wed, Sep 28 | Runtime Analysis of BFS algorithm F22 F21 F19 F118 F17 | [KT, Sec 3.3]
Week 5 recitation notes |
| Fri, Sep 30 | More graph stuff F22 F21 F19 F18 F17 | [KT, Sec 3.3, 3.6] (Project Team Composition Due) Reading Assignment: [KT, Sec 3.3, 3.4, 3.5, 3.6] Reading Assignment: Care package on topological ordering |
| Mon, Oct 3 | Interval Scheduling Problem F22 F21 F19 F18 F17 | [KT, Sec 4.1] |
| Tue, Oct 4 | (HW 3 in) | |
| Wed, Oct 5 | Greedy Algorithm for Interval Scheduling F22 F21 F19 F18 F17 | [KT, Sec 4.1] (Project out) Reading Assignment: [KT, Sec 4.1, 4.2] |
| Fri, Oct 7 | Shortest Path Problem F22 F19 F18 F17 | [KT, Sec 4.4] (Quiz 1) Reading Assignment: Care package on minimizing maximum lateness |
| Mon, Oct 10 | Mid-term exam: I | |
| Tue, Oct 11 | (HW 4 out) | |
| Wed, Oct 12 | Mid-term exam: II | Week 7 recitation notes |
| Fri, Oct 14 | Dijkstra's algorithm F22 F21 F19 F18 F17 | [KT, Sec 4.4] |
| Mon, Oct 17 | Correctness of Dijkstra's Algorithm F22 F21 F19 F18 F17 | [KT, Sec 4.4] Reading Assignment: [KT, Sec 4.4] |
| Tue, Oct 18 | (HW 5 out, HW 4 in) | |
| Wed, Oct 19 | Minimum Spanning Tree F22 F21 F19 F18 F17 | [KT, Sec 4.5] Week 8 recitation notes Reading Assignment: [KT, Sec 4.5] |
| Fri, Oct 21 | Cut Property Lemma F22 F21 F19 F18 F17 | [KT, Sec 4.5] Reading Assignment: [KT, Sec 4.5, 4.6] |
| Mon, Oct 24 | Mergesort F22 F21 F19 F18 F17 | [KT, Sec 5.1] |
| Tue, Oct 25 | (HW 5 in) | |
| Wed, Oct 26 | Solving recurrence relations F22 F21 F19 F18 F17 | [KT, Sec 5.2]
Week 9 recitation notes |
| Fri, Oct 28 | Counting Inversions F22 F21 F19 F18 F17 | [KT, Sec 5.3] (Project (Problem 1 Coding) in) |
| Mon, Oct 31 | Multiplying large integers F22 F21 F19 F18 F17 | [KT, Sec 5.5] (Project (Problem 1 Reflection) in) Reading Assignment: Unraveling the mystery behind the identity |
| Wed, Nov 2 | Closest Pair of Points F22 F21 F19 F18 F17 | [KT, Sec 5.4] Week 10 recitation notes |
| Fri, Nov 4 | Kickass Property Lemma F22 F21 F19 F18 F17 | [KT, Sec 5.4] (Project (Problem 2 Coding) in) |
| Mon, Nov 7 | Weighted Interval Scheduling F22 F21 F19 F17 | [KT, Sec 6.1] (Project (Problem 2 Reflection) in) |
| Tue, Nov 8 | (HW 6 out) | |
| Wed, Nov 9 | Recursive algorithm for weighted interval scheduling problem F22 F21 F19 F17 | [KT, Sec 6.1]
Week 11 recitation notes |
| Fri, Nov 11 | Subset sum problem F22 F21 F19 F18 F17 | [KT, Sec 6.1, 6.2, 6.4] |
| Mon, Nov 14 | Dynamic program for subset sum F22 F21 F19 F18 F17 | [KT, Sec 6.4] |
| Tue, Nov 15 | (HW 7 out, HW 6 in) | |
| Wed, Nov 16 | Shortest path problem F22 F21 F19 F18 F17 | [KT, Sec 6.8]
Week 12 recitation notes |
| Fri, Nov 18 | No Class | Snow Day! |
| Mon, Nov 21 | Bellman-Ford algorithm F22 F21 F19 F18 F17 | [KT, Sec 6.8] |
| Wed, Nov 23 | No class | Fall Recess |
| Fri, Nov 25 | No class | Fall Recess |
| Mon, Nov 28 | The P vs. NP problem F22 F21 F19 | [KT, Sec 8.1] |
| Tue, Nov 29 | (HW 8 out, HW 7 in) | |
| Wed, Nov 30 | More on reductions, P and NP F22 F21 F19 | [KT, Sec 8.1]
Week 14 recitation notes |
| Fri, Dec 2 | NP-Completeness F22 F21 F19 | [KT, Sec 8.3, 8.4] (Project (Problem 3 Coding) in) |
| Mon, Dec 5 | The SAT problem F22 F21 F19 | [KT, Sec. 8.2] (Quiz 2) (Project (Problem 3 Reflection) in) |
| Tue, Dec 6 | (HW 8 in) | |
| Wed, Dec 7 | k-coloring problem F22 F21 F19 | [KT, Sec 8.7] |
| Fri, Dec 9 | k-coloring is NP-complete F22 F21 F19 | [KT, Sec 8.7]
(Project (Problems 4 & 5Coding) in) |
| Mon, Dec 12 | Final Exam | (noon-2:30pm in HOCH 114 (usual classroom)) |
| Tue, Dec 13 | (Project (Problems 4 & 5 Reflection) in) (Project Survey in) |