CSE 331 Fall 2018 Schedule
Previous schedules: 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. Recordings of Fall 2018 lectures are also available from UBLearns.
Date | Topic | Notes |
Mon, Aug 27 | Introduction F18 F17 | (HW 0 out) Week 1 recitation notes |
Wed, Aug 29 | Main Steps in Algorithm Design F18 F17 | |
Fri, Aug 31 | Stable Matching Problem F18 F17 | [KT, Sec 1.1] (HW 0 in by 11:59pm, THURSDAY Aug 30) |
Mon, Sep 3 | No Class | Labor Day Week 2 recitation notes |
Wed, Sep 5 | Algorithms for Stable Matching Problem F18 F17 | [KT, Sec 1.1] |
Fri, Sep 7 | Gale Shapley algorithms F18 F17 | [KT, Sec 1.1] (HW 1 out) Reading Assignment: Support pages on progress measure and pigeon-hole principle |
Mon, Sep 10 | Gale Shalpey algorithm outputs a stable matching F18 F17 | [KT, Sec 1.1] Week 3 recitation notes |
Wed, Sep 12 | Asymptotic Analysis F18 F17 | [KT, Sec 2.1, 2.2] Reading Assignment: All of [KT, Sec 1.1, 1.2, 2.1, 2.2, 2.4] |
Fri, Sep 14 | Analysing runtime of an algorithm F18 F17 | [KT, Sec 2.3] (HW 2 out, HW 1 in by 11:59pm, THURSDAY Sep 13) Reading Assignment: Worst-case runtime analysis notes |
Mon, Sep 17 | Runtime analysis of Gale-Shapley algorithm F18 F17 | [KT, Sec 2.3] Reading Assignment: All of [KT, Chap 2] Week 4 recitation notes |
Wed, Sep 19 | Graph Basics F18 F17 | [KT, Sec 3.1] |
Fri, Sep 21 | Trees F18 F17 | [KT, Sec 3.1] (HW 3 out, HW 2 in by 11:59pm, THURSDAY, Sep 20) |
Mon, Sep 24 | Computing Connected Component F18 F17 | [KT, Sec 3.2] (Mini Project Team Composition Due) Week 5 recitaiton notes |
Wed, Sep 26 | Explore algorithm F18 F17 | [KT, Sec 3.2] |
Fri, Sep 28 | Runtime Analysis of BFS F18 F17 | [KT, Sec 3.3] (HW 4 out, HW 3 in by 11:59pm, THURSDAY, Sep 27) Reading Assignment: [KT, Sec 3.3, 3.4, 3.5] |
Mon, Oct 1 | Topological Ordering F18 F17 | [KT, Sec 3.6] Week 6 recitation notes |
Wed, Oct 3 | Analysis of TopOrd algorithm F18 F17 | [KT, Sec 3.6] |
Fri, Oct 5 | Interval Scheduling F118 F17 | [KT, Sec 4.1] (HW 5 out, HW 4 in by 11:59pm, THURSDAY, Oct 4) |
Mon, Oct 8 | Greedy algorithm for interval scheduling F18 F17 | [KT, Sec 4.1] (Quiz 1) Week 7 recitation notes |
Wed, Oct 10 | Correctness of greedy algorithm F18 F17 | [KT, Sec 4.2] |
Fri, Oct 12 | Minimizing maximum lateness F18 F17 | [KT, Sec 4.2] ( HW 5 in by 11:59pm, THURSDAY, Oct 11) |
Mon, Oct 15 | Exams postponed due to fire alarm in class | |
Wed, Oct 17 | Mid-term exam: I | |
Fri, Oct 19 | Mid-term exam: II | |
Mon, Oct 22 | Greedy algorithm for minimizing maxiumum lateness F18 F17 | [KT, Sec 4.2] Week 8 recitation notes |
Wed, Oct 24 | Exchange argument F18 F17 | [KT, Sec 4.4] |
Fri, Oct 26 | Shortest Path Problem F18 F17 | [KT, Sec 4.4] (HW 6 out) |
Mon, Oct 29 | Dijkstra's Algorithm F18 F17 | [KT, Sec 4.4] Week 9 recitation notes |
Wed, Oct 31 | Minimum Spanning Tree F18 F17 | [KT, Sec 4.5] |
Fri, Nov 2 | Cut Property Lemma F18 F17 | [KT, Sec 4.5] (HW 7 out, HW 6 in by 11:59pm, THURSDAY, Nov 1) |
Mon, Nov 5 | Mergesort F18 F17 | [KT, Sec 5.1] (Mini Project video due) Week 10 recitation notes Reading Assignment : [KT, Sec 4.5, 4.6] |
Wed, Nov 7 | Runtime analysis of Mergesort F18 F17 | [KT, Sec 5.1, 5.2] (Mini Project survey due) |
Fri, Nov 9 | Integer Multiplication F18 F17 | [KT, Sec 5.5] (HW 8 out, HW 7 in by 11:59pm, THURSDAY, Nov 8) Reading Assignment: Unraveling the mystery behind the identity |
Mon, Nov 12 | Couting Inversions F18 F17 | [KT, Sec 5.3] Week 11 recitation notes |
Wed, Nov 14 | Closest Pair of Points F18 F17 | [KT, Sec 5.4] |
Fri, Nov 16 | Kickass Property Lemma F18 F17 | [KT, Sec 5.4] (HW 9 out, HW 8 in by 11:59pm, THURSDAY, Nov 15) |
Mon, Nov 19 | Weighted Interval Scheduling F18 F17 | [KT, Sec 6.1] Week 12 recitation notes |
Wed, Nov 21 | No class | Fall Recess |
Fri, Nov 23 | No class | Fall Recess |
Mon, Nov 26 | Dynamic program for weighted interval scheduling F18 F17 | [KT, Sec 6.1, 6.2] Week 13 recitation notes |
Wed, Nov 28 | Shortest path problem F18 F17 | [KT, Sec 6.8] |
Fri, Nov 30 | Bellman-Ford algorithm F18 F17 | [KT, Sec 6.8] (HW 10 out, HW 9 in by 11:59pm, THURSDAY, Nov 29) |
Mon, Dec 3 | More on Bellman-Ford F18 F17 | (Quiz 2) Week 14 recitation notes |
Wed, Dec 5 | Wrapup F18 | |
Fri, Dec 7 | Q & A Session F18 | (HW 10 in by 11:59pm, THURSDAY, Dec 6) |
Mon, Dec 10 | Final Exam | (8:30am-11:00am in Norton 112 (usual classroom)) |