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