CSE 331 Spring 2024 Schedule
Previous schedules: 2023 (Fall) 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. Recordings of Spring 2024 lectures will be available from UBLearns.
| Date | Topic | Notes |
| Week 1 Wed, Jan 24 | Introduction F23 F22 F21 S21 S20 |
Reading Assignment: HW0 Notes
(HW 0 out) |
| Fri, Jan 26 | Main Steps in Algorithm Design F23 F22 F21 S21 S20 | |
| Week 2 Mon, Jan 29 | Stable Matching Problem F23 F22 F21 S21 S20 | [KT, Sec 1.1]
Week 2 recitation notes |
| Wed, Jan 31 | Perfect Matchings F23 F22 F21 S21 S20 | [KT, Sec 1.1] (HW 0 in) |
| Fri, Feb 2 | Algorithms for stable matching problem F22 F21 S21 S20 | [KT, Sec 1.1] (HW 1 out) |
| Week 3 Mon, Feb 5 | Gale Shapley algorithm F23 F22 F21 S21 S20 | [KT, Sec 1.1]
Week 3 recitation notes Reading Assignment: Pigeonhole principle Reading Assignment: Asymptotic notation care package |
| Wed, Feb 7 | Gale Shapley algorithm outputs a stable matching F23 F22 F21 S21 S20 | [KT, Sec 1.1] Reading Assignment: Proof details of GS termination |
| Fri, Feb 9 | Efficient algorithms and asymptotic analysis F23 F22 F21 S21 S20 | <[KT, Sec 1.1]
[KT, Sec 2.3] (HW 2 out, HW 1 in) Reading Assignment: Worst-case runtime analysis notes Reading Assignment: [KT, Sec 1.1, 2.1, 2.2, 2.4] |
| Week 4 Mon, Feb 12 | Runtime Analysis of Gale-Shapley algorithm F23 F22 F21 S21 S20 | Week 4 recitation notes |
| Wed, Feb 14 | Runtime Analysis of GS continued; Graph Basics F23 F22 F21 S21 S20 | [KT, Sec 2.3, 3.1]
|
| Fri, Feb 16 | Computing Connected Component F22 F21 S21 S20 | [KT, Sec 3.2] (HW 3 out, HW 2 in) Reading Assignment: Care package on trees Reading Assignment: BFS by examples |
| Week 5 Mon, Feb 19 | Explore Algorithm F23 F22 F21 S21 S20 S20 | [KT, Sec 3.2] Week 5 recitaiton notes |
| Wed, Feb 21 | Runtime Analysis of BFS algorithm F23 F22 F21 S21 S20 S20 | [KT, Sec 3.3]
|
| Fri, Feb 23 | More graph stuff; Interval Scheduling Problen F23 F22 F21 S21 S20 | (HW 3 in) [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 |
| Week 6 Mon, Feb 26 | Interval Scheduling Problem F23 F22 F21 S21 S20 | [KT, Sec 4.1] (Project Team Composition Due) |
| Wed, Feb 28 | Greedy Algorithm for Interval Scheduling F23 F22 F21 S21 S20 | |
| Fri, Mar 1 | Greedy Algo. for Intv. Sched. outputs an Optimal Solution F23 F22 S21 S20 | Quiz 1 (HW4 Out) [KT, Sec 4.4] Reading Assignment: Care package on minimizing maximum lateness Reading Assignment: [KT, Sec 4.1, 4.2] |
| Week 7 Mon, Mar 4 | Shortest Path Problem F23 F22 F21 S21 S20 | [KT, Sec 4.4] (Project Out) Week 7 recitation notes |
| Wed, Mar 6 | Dijkstra's algorithm F21 | [KT, Sec 4.4] |
| Fri, Mar 8 | Correctness of Dijkstra's Algorithm F23 F22 F21 S21 S20 | [KT, Sec 4.5] (HW4 in) Reading Assignment: [KT, Sec 4.4, 4.5] |
| Week 8 Mon, Mar 11 | Minimum Spanning Tree F23 F22 F21 S21 S20 | [KT, Sec 4.5] Reading Assignment: [KT, Sec 4.5, 4.6] |
| Wed, Mar 13 | Mid-term exam: I | |
| Fri, Mar 15 | Mid-term exam: II | |
| Week 9 Mon, Mar 18 - Fri, Mar 22 | No Class | Spring Break
HW5 out on Friday, Mar 22 |
| Week 10 Mon, Mar 25 | Cut Property Lemma F23 F22 F21 S21 S20 | [KT, Sec 5.1]
Week 10 recitation notes |
| Wed, Mar 27 | Cut Property Lemma; Mergesort F23 F22 F21 S21 S20 | [KT, Sec 5.1, 5.2] |
| Fri, Mar 29 | Solving recurrence relations F23 F22 F21 S21 S20 | [KT, Sec 5.3]
[KT, Sec 5.5] (HW 5 in) (Project (Problem 1 Coding) in) |
| Week 11 Mon, Apr 1 | Recurrence; Counting Inversions F23 F22 F21 S21 S20 |
(Project (Problem 1 Reflection) in)
Week 11 recitation notes Reading Assignment: Unraveling the mystery behind the identity |
| Wed, Apr 3 | Multiplying large integers F23 F22 F21 S21 S20 | [KT, Sec 5.4] |
| Fri, Apr 5 | Closest Pair of Points F23 F22 F21 S21 S20 | [KT, Sec 5.4] (Project (Problem 2 Coding) in)
(HW 6 out) |
| Week 12 Mon, Apr 8 | Closest Pair of Points Cont. F23 F22 F21 S21 S20 | [KT, Sec 6.1] (Project (Problem 2 Reflection) in) Week 12 recitation notes |
| Wed, Apr 10 | Weighted Interval Scheduling F23 F22 F21 S21 S20 | [KT, Sec 6.1]
|
| Fri, Apr 12 | Recursive algo. for weighted intl. sched. problem F23 F22 F21 S21 S20 | [KT, Sec 6.1, 6.2, 6.4] [KT, Sec 6.4] (HW 7 out, HW 6 in) |
| Week 13 Mon, Apr 15 | weight. intl. sched. prob. cont. F23 F22 F21 S21 S20 | Week 13 recitation notes |
| Wed, Apr 17 | Subset sum problem F23 F22 F21 S21 S20 | [KT, Sec 6.8] |
| Fri, Apr 19 | Shortest path problem F23 F22 F21 S21 S20 | [KT, Sec 6.8] ( HW 7 in ) |
| Week 14 Mon, Apr 22 | Bellman-Ford algorithm F22 F21 S21 S20 | [KT, Sec 8.1] |
| Wed, Apr 24 | The P vs. NP problem F23 F22 F21 S21 S20 | [KT, Sec 8.1] |
| Fri, Apr 26 | More on reductions F23 F22 F21 S21 S20 | [KT, Sec 8.2] (Quiz 2) (HW 8 out) (Project (Problem 3 Coding) in)
|
| Week 15 Mon, Apr 29 | NP-Completeness F23 F22 F21 S21 S20 | [KT, Sec. 8.3, 8.4] (Project (Problem 3 Reflection) in) Week 15 recitation notes |
| Wed, May 1 | The SAT problem F23 F22 F21 S21 S20 | [KT, Sec 8.7] |
| Fri, May 3 | k-coloring problem F22 F21 S21 S20 | [KT, Sec 8.7] (HW 8 in) (Project (Problems 4 & 5 Coding) in)
|
| Week 16 Mon, May 6 | k-coloring is NP-complete F23 F22 F21 S21 S20 | (Project (Problems 4 & 5 Reflection) in) (Project Survey in) |
| Tues, May 14 | Final Exam | (11:45am-2:45pm in Norton 190) |