Any content that's colored light gray is tentative and subject to change.
Homework sets will be available on this course's Canvas page (you will need to click through to Gradescope). Please read the policies section of the course website for submission instructions, the lateness policy (which is absolutely strict), grading standards, and the academic honor principle.
Lectures, Exams, and Submissions Due
In the table below, references are to the three designated reference books. Notation like "[KT 2.1]" refers to section 2.1 of the Kleinberg-Tardos book. Similarly, [CLRS Ch 2] refers to chapter 2 of the Cormen-Leiserson-Rivest-Stein book and [Eri] refers to the Erickson book.
| # | Date | Class Topics / Other Events | References |
|---|---|---|---|
| 1 |
Tue Sep 12 | Analyzing time complexity ● What is a unit cost operation? ● Arrays, lists, dictionaries, binary trees ● Binary search | [KT 2.1]; [CLRS 2.1, 2.2]; [Eri Ch 0] |
| 2 |
Wed Sep 13 | x-hour not used | |
| 3 |
Thu Sep 14 | Asymptotic notation: O, Ω, Θ ● Proving algorithm correctness using invariants ● Recursion | [CLRS Ch 2]; [Eri 1.1—1.6] |
| S |
Mon Sep 18 | Homework 1 due by 22:00 | |
| 4 |
Tue Sep 19 | Efficient sorting ● InsertionSort and MergeSort ● QuickSort and HeapSort (teaser) | [CLRS Ch 2, 6.4, 7.2]; [KT 2.4, 2.5]; [Eri 1.4, 1.5] (notes) |
| 5 |
Wed Sep 20 | (x-hour) Administrivia ● How to succeed in this course | course website and canvas |
| 6 |
Thu Sep 21 | Graphs and digraphs ● Adjacency list/matrix ● Graph traversal and its properties | [CLRS 20.1—20.2]; [KT 3.1—3.3]; [Eri Ch 5] (notes) |
| S |
Mon Sep 25 | Homework 2 due by 22:00 | |
| 7 |
Tue Sep 26 | Breadth-first search ● Shortest paths (unweighted) ● Depth-first search | [Eri 6.1]; [KT 3.3—3.6]; [CLRS 20.2—20.3] (notes) |
| 8 |
Wed Sep 27 | (x-hour) Parenthesis theorem and Path lemma for DFS ● DAGs and Cycle finding | [Eri 6.1—6.2]; [KT 3.3—3.6]; [CLRS 20.3—20.4] |
| 9 |
Thu Sep 28 | Topological sort ● Strongly connected components | [Eri 6.3, 6.5, 6.6]; [CLRS 20.4—20.5] (notes) |
| S |
Mon Oct 02 | Homework 3 due by 22:00 | |
| 10 |
Tue Oct 03 | Divide-and-conquer ● MergeSort redux ● Counting inversions ● Karatsuba integer multiplication ● Strassen matrix multiplication | [KT 5.1—5.3, 5.5]; [Eri 1.7, 1.9]; [CLRS Ch 4] |
| 11 |
Wed Oct 04 | x-hour not used | |
| 12 |
Thu Oct 05 | Master theorem/method for recurrences ● Closest pair of points ● Selection in linear time | [Eri 1.8]; [CLRS 9.1, 9.3] (slides) |
| S |
Mon Oct 09 | Homework 4 due by 22:00 | |
| 13 |
Tue Oct 10 | Dynamic programming: Fibonacci numbers, Rod cutting | [Eri 3.1—3.5]; [CLRS 14.1] |
| Q |
Wed Oct 11 | **Midterm 1** from 17:30 to 20:30 | |
| 14 |
Thu Oct 12 | Systematically presenting a DP algorithm ● Weighted interval scheduling ● Longest common subsequence | [KT 6.1, 6.2]; [CLRS 14.2—14.4] (notes) |
| S |
Mon Oct 16 | Homework 5 due by 22:00 | |
| 15 |
Tue Oct 17 | Yet more DP: Matrix chain multiplication ● DP and graph algorithms ● Bellman-Ford SSSP | [Eri 8.7, 9.8] (notes) |
| 16 |
Wed Oct 18 | x-hour not used | |
| 17 |
Thu Oct 19 | Floyd-Warshall APSP ● Subset-Sum and pseudopolynomial time ● DP wrap-up | [KT 6.4]; [Eri 3.8] (notes) |
| S |
Mon Oct 23 | Homework 6 due by 22:00 | |
| 18 |
Tue Oct 24 | Generic relaxation-based SSSP algorithms ● Correctness of Bellman-Ford algorithm ● Dijkstra's algorithm and its correctness | [KT 4.4]; [CLRS Ch 22]; [Eri 8.6] (notes) |
| 19 |
Wed Oct 25 | x-hr not used | |
| 20 |
Thu Oct 26 | Minimum spanning trees and Prim's algorithm ● Cut property and correctness of Prim ● Priority queues and time complexity | [KT 4.5]; [CLRS Ch 21]; [Eri 7.1—7.4] (notes) |
| S |
Mon Oct 30 | Homework 7 due by 22:00 | |
| 21 |
Tue Oct 31 | Kruskal's algorithm ● Slack / catch up | [KT 4.5]; [CLRS Ch 21]; [Eri 7.5] |
| Q |
Wed Nov 01 | **Midterm 2** from 17:30 to 20:30 | |
| 22 |
Thu Nov 02 | Flows and cuts I | [Eri Ch 10] |
| S |
Mon Nov 06 | Homework 8 due by 22:00 | |
| 23 |
Tue Nov 07 | Flows and cuts II | [Eri Ch 10] |
| 24 |
Wed Nov 08 | x-hour not used | |
| 25 |
Thu Nov 09 | Flows and cuts III | [Eri Ch 11] |
| S |
Mon Nov 13 | Homework 9 due by 22:00 | |
| 26 |
Tue Nov 14 | Tying up loose ends; Wrap-up | (no refs) |
The **final exam** has been scheduled by the Registrar's Office:
11:30 to 14:30 on Sun Nov 19, in ECSC 005.
Please do not schedule anything during the X-hour: we may need to use one at short notice.
Reading Homework
There is reading homework associated with every class, which consists of reading at least one of the reference book sections listed, plus any slides or notes linked from the table above. Sometimes, there won't be any corresponding book section, in which case you should review your notes from class instead.
There is nothing to submit and no grade for this reading homework, but I assume that you will nevertheless do the homework on time, every time.