CSE 331 Fall 2024 Schedule
Previous schedules: 2024 (Spring) , 2023 (Fall), 2023 (Spring) , 2022 (Fall), 2022 (Spring) , 2021 (Fall), 2021 (Spring) , 2020 , 2019.
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, Fall 2021, Fall 2022 and Fall 2023. Recordings of Fall 2024 lectures are also available from UBLearns.
| Date | Topic | Notes |
| Mon, Aug 26 | Introduction F24 F23 F22 F21 F19 | Syllabus Walkthrough: |
| Tue, Aug 27 | (HW 0 out) | |
| Wed, Aug 28 | Let's do a proof! F24 F23 F22 F21 F19 | Week 1 recitation notes |
| Fri, Aug 30 | Halting is Unsolvable F24 F23 F22 F21 F19 | |
| Mon, Sep 2 | No Class | Labor Day |
| Tue, Sep 3 | (HW 0 in) | |
| Wed, Sep 4 | Perfect Matchings F24 F23 F22 F21 F19 | [KT, Sec 1.1]
Week 2 recitation notes |
| Fri, Sep 6 | Stable matching problem F24 F23 F22 F21 F19 | [KT, Sec 1.1] |
| Mon, Sep 9 | Gale Shapley algorithm F24 F23 F22 F21 F19 | [KT, Sec 1.1] Reading Assignment: Pigeonhole principle Reading Assignment: Asymptotic notation care package |
| Tue, Sep 10 | (HW 1 out) | |
| Wed, Sep 11 | Gale Shapley algorithm outputs a stable matching F24 F23 F22 F21 F19 | [KT, Sec 1.1] Reading Assignment: Proof details of GS termination Week 3 recitation notes |
| Fri, Sep 13 | Proving GS is correct F24 F23 F22 F21 F19 | [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 16 | Runtime Analysis of Gale-Shapley algorithm F24 F23 F22 F21 F19 | [KT, Sec 2.3] |
| Tue, Sep 17 | (HW 2 out, HW 1 in) | |
| Wed, Sep 18 | Runtime Analysis of Gale-Shapley algorithm - II F24 F23 F22 F21 F19 | [KT, Sec 2.3]
Week 4 recitation notes |
| Fri, Sep 20 | Graph Basics F24 F22 F21 F19 | [KT, Sec 3.1] (Project Team Composition Due) Reading Assignment: Care package on trees Reading Assignment: BFS by examples |
| Mon, Sep 23 | Breadth First Search F24 F23 F22 F21 F19 | [KT, Sec 3.2] |
| Tue, Sep 24 | (HW 3 out, HW 2 in) | |
| Wed, Sep 25 | Explore algorithm F24 F23 F22 F21 F19 | [KT, Sec 3.3] Week 5 recitation notes |
| Fri, Sep 27 | Runtime Analysis of BFS algorithm F24 F23 F22 F21 F19 | [KT, Sec 3.3] Reading Assignment: [KT, Sec 3.3, 3.4, 3.5, 3.6] Reading Assignment: Care package on topological ordering |
| Mon, Sep 30 | More graph stuff F24 F23 F22 F21 F19 | [KT, Sec 3.3, 3.6] (Quiz 1) (Group Registration on Autolab due) |
| Tue, Oct 1 | (HW 3 in) | |
| Wed, Oct 2 | Interval Scheduling Problem F24 F23 F22 F21 F19 | [KT, Sec 4.1] (Project out) Reading Assignment: [KT, Sec 4.1, 4.2] |
| Fri, Oct 4 | Greedy Algorithm for Interval Scheduling F24 F23 F22 F19 | [KT, Sec 4.1] Reading Assignment: Care package on minimizing maximum lateness |
| Mon, Oct 7 | Mid-term exam: I | |
| Wed, Oct 9 | Mid-term exam: II | Week 7 recitation notes |
| Fri, Oct 11 | Shortest Path Problem F24 F23 F22 F21 F19 | [KT, Sec 4.4] |
| Mon, Oct 14 | No class | Fall break! |
| Tue, Oct 15 | (HW 4 out) | |
| Wed, Oct 16 | Dijkstra's algorithm F24 F23 F22 F21 F19 | [KT, Sec 4.4] Week 8 recitation notes |
| Fri, Oct 18 | Correctness of Dijkstra's Algorithm F24 F23 F22 F21 F19 | [KT, Sec 4.4] Reading Assignment: [KT, Sec 4.4] |
| Mon, Oct 21 | Minimum Spanning Tree F24 F23 F22 F21 F19 | [KT, Sec 4.5] |
| Tue, Oct 22 | (HW 4 in, HW 5 out) | |
| Wed, Oct 23 | Cut Property Lemma F24 F23 F22 F21 F19 | [KT, Sec 4.5]
Week 9 recitation notes Reading Assignment: [KT, Sec 4.5, 4.6] |
| Fri, Oct 25 | Mergesort F24 F23 F22 F21 F19 | [KT, Sec 5.1] |
| Mon, Oct 28 | Solving recurrence relations F24 F23 F22 F21 F19 | [KT, Sec 5.1] |
| Tue, Oct 29 | (HW 5 in) | |
| Wed, Oct 30 | Counting Inversions F24 F23 F22 F21 F19 | [KT, Sec 5.3] Reading Assignment: [KT, Sec 5.2] Week 10 recitation notes |
| Fri, Nov 1 | Multiplying large integers F24 F23 F22 F21 F19 | [KT, Sec 5.5] (Project (Problems 1 & 2 Coding) in)
Reading Assignment: Unraveling the mystery behind the identity |
| Mon, Nov 4 | Closest Pair of Points F24 F23 F22 F21 F19 | [KT, Sec 5.4] (Project (Problems 1 & 2 Reflection) in) |
| Tue, Nov 5 | (HW 6 out) | |
| Wed, Nov 6 | Kickass Property Lemma F24 F23 F22 F21 F19 | [KT, Sec 5.4]
Week 11 recitation notes |
| Fri, Nov 8 | Weighted Interval Scheduling F24 F23 F22 F21 F19 | [KT, Sec 6.1] |
| Mon, Nov 11 | Recursive algorithm for weighted interval scheduling problem F24 F23 F22 F21 F19 | [KT, Sec 6.1, 6.2] |
| Tue, Nov 12 | (HW 7 out, HW 6 in) | |
| Wed, Nov 13 | Iterative algorithm for weighted interval scheduling problem F24 F23 F22 F21 F19 | [KT, Sec 6.1, 6.2]
Week 12 recitation notes |
| Fri, Nov 15 | Subset sum problem F24 F23 F22 F21 F19 | [KT, Sec 6.4] |
| Mon, Nov 18 | Shortest path problem F24 F23 F22 F21 F19 | [KT, Sec 6.8] Reading Assignment: [KT, Sec 6.4] |
| Tue, Nov 19 | (HW 8 out, HW 7 in) | |
| Wed, Nov 20 | Bellman-Ford Algorithm F24 F23 F22 F21 F19 | [KT, Sec 6.8] Week 13 recitation notes |
| Fri, Nov 22 | Reductions F24 F23 F22 F21 F19 | [KT, Sec 8.1] |
| Mon, Nov 25 | P and NP F24 F23 F22 F21 F19 | [KT, Sec 8.3, 8.4] (Project (Problem 3 Coding) in) |
| Wed, Nov 27 | No class | Fall Break |
| Fri, Nov 29 | No class | Fall Break |
| Mon, Dec 2 | NP Completeness F24 F23 F22 F21 F19 | [KT, Sec. 8.4] (Quiz 2) (Project (Problem 3 Reflection) in) |
| Tue, Dec 3 | (HW 8 in) | |
| Wed, Dec 4 | Satisfiability F24 F23 F22 F21 F19 | [KT, Sec 8.2] |
| Fri, Dec 6 | k-coloring F24 F23 F22 F21 F19 | [KT, Sec 8.2, 8.7]
(Project (Problems 4 & 5Coding) in) |
| Mon, Dec 9 | Wrapup F24 F23 | [KT, Sec 8.7] |
| Tue, Dec 10 | (Project (Problems 4 & 5 Reflection) in) (Project Survey in) |
Tue, Dec 17 | Final Exam | (8:30-11:00am in Knox 109) |