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