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