Date | Topic | Notes |
Mon, Aug 29 | Introduction [Slides: PDF, PPTX] | (HW 0 out) Pre-lecture video |
Wed, Aug 31 | Main Steps in Algorithm Design ([Slides: PDF, PPT], Notes) | Pre-lecture video |
Fri, Sep 2 | Stable Matching Problem ([Slides: PDF, PPT], Notes) | [KT, Sec 1.1] (HW 0 in) Pre-lecture video |
Mon, Sep 5 | No Class | Labor Day Recitation 1 |
Wed, Sep 7 | Gale Shapley algorithm ([Slides: PDF, PPT], Notes) | [KT, Sec 1.1] Pre-lecture video |
Fri, Sep 9 | Correctness of Gale Shapley algorithms ([Slides: PDF, PPT], Notes) | [KT, Sec 1.1] (HW 1 out) Pre-lecture video Reading Assignment: Sections 6 and 7 in these notes |
Mon, Sep 12 | Gale Shalpey algorithm outputs a stable matching ([Slides: PDF, PPT], Notes) | [KT, Sec 1.1] Career Services Presentations slides Recitation 2 |
Wed, Sep 14 | Asymptotic Analysis ([Slides: PDF, PPT], Notes) | [KT, Sec 2.1, 2.2] Pre-lecture video Reading Assignment: All of [KT, Sec 1.1] |
Fri, Sep 16 | Analysing runtime of an algorithm ([Slides: PDF, PPT], Notes) | [KT, Sec 2.3] (HW 2 out, HW 1 in) Pre-lecture video Reading Assignment: Worst-case runtime analysis notes |
Mon, Sep 19 | Runtime analysis of Gale-Shapley algorithm ([Slides: PDF, PPT], Notes) | [KT, Sec 2.3] Pre-lecture video Reading Assignment: All of [KT, Chap 2] Recitation 3 |
Wed, Sep 21 | Graph Basics ([Slides: PDF, PPT], Notes) | [KT, Sec 3.1] Pre-lecture video |
Fri, Sep 23 | Trees ([Slides: PDF, PPT], Notes) | [KT, Sec 3.1] (HW 3 out, HW 2 in) Pre-lecture video |
Mon, Sep 26 | Computing Connected Component ([Slides: PDF, PPT], Notes) | [KT, Sec 3.2] (Mini Project Team Composition Due) Pre-lecture video Recitation 4 |
Wed, Sep 28 | Graph Representation ([Slides: PDF, PPT], Notes) | [KT, Sec 3.2] |
Fri, Sep 30 | Runtime Analysis of BFS and DFS ([Slides: PDF, PPT], Notes) | [KT, Sec 3.3] (HW 4 out, HW 3 in) Pre-lecture video Reading Assignment: [KT, Sec 3.3, 3.4, 3.5] |
Mon, Oct 3 | Topological Ordering ([Slides: PDF, PPT], Notes | [KT, Sec 3.6] Recitation 5 |
Wed, Oct 5 | Analysis of TopOrd algorithm ([Slides: PDF, PPT], Notes) | [KT, Sec 3.6] (Mini Project Pitch Due) |
Fri, Oct 7 | Interval Scheduling ([Slides: PDF, PPT], Notes) | [KT, Sec 4.1] (HW 5 out, HW 4 in) |
Mon, Oct 10 | Greedy algorithm for interval scheduling ([Slides: PDF, PPT], Notes) | [KT, Sec 4.1] (Quiz 1) Recitation 6 |
Wed, Oct 12 | Scheduling to minimize maximum lateness ([Slides: PDF, PPT], Notes) | [KT, Sec 4.2] |
Fri, Oct 14 | Greedy scheduling algorithm ([Slides: PDF, PPT], Notes) | [KT, Sec 4.2] ( HW 5 in) |
Mon, Oct 17 | Mid-term exam: I | |
Wed, Oct 19 | Mid-term exam: II | |
Fri, Oct 21 | Exchange argument ([Slides: PDF, PPT], Notes) | [KT, Sec 4.2] |
Mon, Oct 24 | Shortest path problem ([Slides: PDF, PPT], Notes) | [KT, Sec 4.4] ) Recitation 8 |
Wed, Oct 26 | Dijkstra's algorithm ([Slides: PDF, PPT], Notes) | [KT, Sec 4.4] |
Fri, Oct 28 | Minimum Spanning Tree ([Slides: PDF, PPT], Notes) | [KT, Sec 4.5] (HW 6 out) |
Mon, Oct 31 | Cut Property Lemma ([Slides: PDF, PPT], Notes) | [KT, Sec 4.5] Recitation 9 |
Wed, Nov 2 | Mergesort ([Slides: PDF, PPT], Notes) | [KT, Sec 5.1] Reading Assignment : [KT, Sec 4.5, 4.6] |
Fri, Nov 4 | Analysis of Mergesort ([Slides: PDF, PPT], Notes) | [KT, Sec 5.1] (HW 7 out, HW 6 in) |
Mon, Nov 7 | Integer Multiplication ([Slides: PDF, PPT], Notes) | [KT, Sec 5.5] Recitation 10 |
Wed, Nov 9 | Counting inversions ([Slides: PDF, PPT], Notes) | [KT, Sec 5.3] |
Fri, Nov 11 | Closest pair of points ([Slides: PDF, PPT], Notes) | [KT, Sec 5.4] (HW 8 out, HW 7 in) |
Mon, Nov 14 | Kickass Property Lemma ([Slides: PDF, PPT], Notes) | [KT, Sec 5.4] (Mini Project video due) Recitation 11 |
Wed, Nov 16 | Weighted Interval Scheduling ([Slides: PDF, PPT], Notes) | [KT, Sec 6.1] |
Fri, Nov 18 | Dynamic program for weighted interval scheduling ([Slides: PDF, PPT], Notes) | [KT, Sec 6.1, 6.2] (HW 9 out, HW 8 in) |
Mon, Nov 21 | Subset sum problem ([Slides: PDF, PPT], Notes) | [KT, Sec 6.4] Recitation 12 |
Wed, Nov 23 | No class | Fall Recess |
Fri, Nov 25 | No class | Fall Recess |
Mon, Nov 28 | Dynamic program for subset sum ([Slides: PDF, PPT], Notes) | [KT, Sec 6.4] Recitation 13 Recitation 13 by Zulkar |
Wed, Nov 30 | Shortest path problem ([Slides: PDF, PPT], Notes) | [KT, Sec 6.8] |
Fri, Dec 2 | Bellman-Ford algorithm ([Slides: PDF, PPT], Notes) | [KT, Sec 6.8] (HW 10 out, HW 9 in) |
Mon, Dec 5 | NP-completeness ([Slides: PDF, PPT]) | (Quiz 2) |
Wed, Dec 7 | Wrapup ([Slides: PDF, PPT], Notes) | |
Fri, Dec 9 | Presentations | (HW 10 in) |
Fri, Dec 16 | Final Exam | (noon-2:30pm) |