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