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