CSE 331 Spring 2025 Schedule
Previous schedules: 2024 (Fall), 2024 (Spring) , 2023 (Fall), 2023 (Spring) , 2022 (Fall), 2022 (Spring) , 2021 (Fall), 2021 (Spring) , 2020 .
Under Construction
This page is still under construction. In particular, nothing here is final while this sign still remains here.
Future Lectures
The topics for lectures in the future are tentative and subject to change.
Recordings of Tom's Spring 2025 lectures are available on Panopto. Recordings of Yorah's Spring 2025 lectures are available on UBLearns.
Lecture slides for Yorah's classes Lecture slides for Tom's classes
Legend
Lecture slides in PDF format.
Lecture slides in PPTX format.
Lecture notes.
Video recording of the lecture.
Pre-lecture video.
Notation help.
| Date | Topic | Notes |
| Wed, Jan 22 | Introduction F24 F23 F22 F21 F19 | Syllabus Walkthrough: |
| Fri, Jan 24 | Let's do a proof! F24 F23 F22 F21 F19 | |
| Mon, Jan 27 | Halting is Unsolvable F24 F23 F22 F21 F19 | |
| Tue, Jan 28 | (HW 0 out) | |
| Wed, Jan 29 | Perfect Matchings F24 F23 F22 F21 F19 | [KT, Sec 1.1]
Week 2 recitation notes |
| Fri, Jan 31 | Stable matching problem F24 F23 F22 F21 F19 | [KT, Sec 1.1] |
| Mon, Feb 3 | Gale Shapley algorithm F24 F23 F22 F21 F19 | [KT, Sec 1.1] Reading Assignment: Pigeonhole principle Reading Assignment: Asymptotic notation care package |
| Tue, Feb 4 | (HW 0 in, HW 1 out) | |
| Wed, Feb 5 | 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, Feb 7 | 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, Feb 10 | Runtime Analysis of Gale-Shapley algorithm F24 F23 F22 F21 F19 | [KT, Sec 2.3] |
| Tue, Feb 11 | (HW 1 in, WH 2 out) | |
| Wed, Feb 12 | Runtime Analysis of Gale-Shapley algorithm - II F24 F23 F22 F21 F19 | [KT, Sec 2.3]
Week 4 recitation notes |
| Fri, Feb 14 | Graph Basics F24 F22 F21 F19 | [KT, Sec 3.1] Reading Assignment: Care package on trees Reading Assignment: BFS by examples |
| Mon, Feb 17 | Breadth First Search F24 F23 F22 F21 F19 | [KT, Sec 3.2] |
| Tue, Feb 18 | (HW 2 in, HW 3 out) | |
| Wed, Feb 19 | Explore algorithm F24 F23 F22 F21 F19 | [KT, Sec 3.3] Week 5 recitation notes |
| Fri, Feb 21 | Runtime Analysis of BFS algorithm F24 F23 F22 F21 F19 | [KT, Sec 3.3] (Project Team Registration Open) Reading Assignment: [KT, Sec 3.3, 3.4, 3.5, 3.6] Reading Assignment: Care package on topological ordering |
| Mon, Feb 24 | More graph stuff F24 F23 F22 F21 F19 | [KT, Sec 3.3, 3.6] |
| Tue, Feb 25 | (HW 3 in) | |
| Wed, Feb 26 | Interval Scheduling Problem F24 F23 F22 F21 F19 | [KT, Sec 4.1] Reading Assignment: [KT, Sec 4.1, 4.2] |
| Fri, Feb 28 | Greedy Algorithm for Interval Scheduling F24 F23 F22 F19 | [KT, Sec 4.1] Reading Assignment: Care package on minimizing maximum lateness |
| Mon, Mar 3 | Shortest Path Problem F24 F23 F22 F21 F19 | [KT, Sec 4.4] (Group Registration on Autolab due) (Project out) (Quiz 1) |
| Tue, Mar 4 | (HW 4 out) | |
| Wed, Mar 5 | Dijkstra's algorithm F24 F23 F22 F21 F19 | [KT, Sec 4.4] Week 7 recitation notes |
| Fri, Mar 7 | Correctness of Dijkstra's Algorithm F24 F23 F22 F21 F19 | [KT, Sec 4.4] Reading Assignment: [KT, Sec 4.4] |
| Mon, Mar 10 | Review class | |
| Tue, Mar 11 | (HW 4 in) | |
| Wed, Mar 12 | 2nd Review class? | Week 8 recitation notes | Thurs, Mar 13 | Midterm exam, 7:00pm-8:50pm, Knox 20 |
| Fri, Mar 14 | Preview: Karatsuba Multiplication | Day before Spring Break! |
| Week of Mar 17-21 | Spring Recess | No class |
| Mon, Mar 24 | Minimum Spanning Tree F24 F23 F22 F21 F19 | [KT, Sec 4.5] |
| Tue, Mar 25 | (HW 5 out) | |
| Wed, Mar 26 | 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, Mar 28 | Mergesort F24 F23 F22 F21 F19 | [KT, Sec 5.1] (Project Problem 1 Coding in)
|
| Mon, Mar 31 | Solving recurrence relations F24 F23 F22 F21 F19 | [KT, Sec 5.1] |
| Tue, Apr 1 | (HW 5 in) (Project Problem 1 Reflection in) |
|
| Wed, Apr 2 | Counting Inversions F24 F23 F22 F21 F19 | [KT, Sec 5.3] Reading Assignment: [KT, Sec 5.2] Week 10 recitation notes |
| Fri, Apr 4 | Multiplying large integers F24 F23 F22 F21 F19 | [KT, Sec 5.5] (Project Problem 2 Coding in)
Reading Assignment: Unraveling the mystery behind the identity |
| Mon, Apr 7 | Closest Pair of Points F24 F23 F22 F21 F19 | [KT, Sec 5.4] |
| Tue, Apr 8 | (HW 6 out) (Project Problems 2 Reflection in) |
|
| Wed, Apr 9 | Kickass Property Lemma F24 F23 F22 F21 F19 | [KT, Sec 5.4]
Week 11 recitation notes |
| Fri, Apr 11 | Weighted Interval Scheduling F24 F23 F22 F21 F19 | [KT, Sec 6.1] (Project Problem 3 Coding in)
|
| Mon, Apr 14 | Recursive algorithm for weighted interval scheduling problem F24 F23 F22 F21 F19 | [KT, Sec 6.1, 6.2] |
| Tue, Apr 15 | (HW 6 in, HW 7 out) (Project Problem 3 Reflection in) |
|
| Wed, Apr 16 | Iterative algorithm for weighted interval scheduling problem F24 F23 F22 F21 F19 | [KT, Sec 6.1, 6.2]
Week 12 recitation notes |
| Fri, Apr 18 | Subset sum problem F24 F23 F22 F21 F19 | [KT, Sec 6.4] (Project Problem 4 Coding> in)
|
| Mon, Apr 21 | Shortest path problem F24 F23 F22 F21 F19 | [KT, Sec 6.8] Reading Assignment: [KT, Sec 6.4] |
| Tue, Apr 22 | (HW 7 in, HW 8 out)
(Project Problem 4 Reflection in) |
|
| Wed, Apr 23 | Bellman-Ford Algorithm F24 F23 F22 F21 F19 | [KT, Sec 6.8] Week 13 recitation notes |
| Fri, Apr 25 | Reductions F24 F23 F22 F21 F19 | [KT, Sec 8.1]
(Project Problem 5Coding in) |
| Mon, Apr 28 | P and NP F24 F23 F22 F21 F19 | [KT, Sec 8.3, 8.4] |
| Tue, Apr 29 | (HW 8 in) (Project Problem 5 Reflection in) |
|
| Wed, Apr 30 | NP Completeness F24 F23 F22 F21 F19 | [KT, Sec. 8.4] (Quiz 2) (Project Survey in) |
| Fri, May 2 | Satisfiability F24 F23 F22 F21 F19 | [KT, Sec 8.2] |
| Mon, May 5 | Last lecture: k-coloring and wrap-up F24 F23 F22 F21 F19 Wrapup F24 Wrapup F23 | [KT, Sec 8.2, 8.7] |
| Tue, May 6 | Thu, May 8 | Final Exam | (tentative! 3:30pm-6:30pm in Knox 20)(tentative!) |