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 Jan 06 | 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 |
Thu Jan 08 | Asymptotic notation: O, Ω, Θ ● Proving algorithm correctness using invariants ● Recursion | [CLRS Ch 2]; [Eri 1.1—1.6] (notes) |
| X |
Fri Jan 09 | Administrivia ● How to succeed in this course ● Problem solving session (optionally until 17:30) | course website and canvas |
| S |
Mon Jan 12 | Homework 1 due by 22:00 | |
| 3 |
Tue Jan 13 | Efficient sorting ● InsertionSort and MergeSort ● QuickSort and HeapSort | [CLRS Ch 2, 6.4, 7.2]; [KT 2.4, 2.5]; [Eri 1.4, 1.5] (notes) |
| 4 |
Thu Jan 15 | Graphs and digraphs ● Adjacency list/matrix ● Graph traversal and its properties ● Breadth-first search | [CLRS 20.1—20.2]; [KT 3.1—3.3]; [Eri Ch 5] (notes) |
| X |
Fri Jan 16 | Catch-up ● Problem solving session (optionally until 17:30) | same as above (notes) |
| S |
Mon Jan 19 | Homework 2 due by 22:00 | |
| 5 |
Tue Jan 20 | Depth-first search ● Parenthesis theorem and white-path theorem ● DAGs and Cycle finding | [Eri 6.1—6.2]; [KT 3.3—3.6]; [CLRS 20.2—20.3] (notes) |
| 6 |
Thu Jan 22 | Topological sort ● Strongly connected components | [Eri 6.3, 6.5, 6.6]; [KT 3.3—3.6]; [CLRS 20.4—20.5] (notes) |
| X |
Fri Jan 23 | Problem solving session (optional extended session until 17:30) | |
| S |
Mon Jan 26 | Homework 3 due by 22:00 | |
| 7 |
Tue Jan 27 | 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] |
| 8 |
Thu Jan 29 | Master theorem/method for recurrences ● Closest pair of points ● Selection in linear time | [KT 5.4]; [Eri 1.8]; [CLRS 9.1, 9.3] (slides) |
| X |
Fri Jan 30 | Problem solving session (optional extended session until 17:30) | |
| S |
Mon Feb 02 | Homework 4 due by 22:00 | |
| 9 |
Tue Feb 03 | Dynamic programming: Fibonacci numbers, Rod cutting | [Eri 3.1—3.5]; [CLRS 14.1] |
| Q |
Wed Feb 04 | **Midterm 1** from 18:30 to 21:30 in Cummings 200 | |
| 10 |
Thu Feb 05 | Systematically presenting a DP algorithm ● Weighted interval scheduling ● Longest common subsequence | [KT 6.1, 6.2]; [CLRS 14.2—14.4] (notes) |
| X |
Fri Feb 06 | Problem solving session (optional extended session until 17:30) | |
| S |
Mon Feb 09 | Homework 5 due by 22:00 | |
| 11 |
Tue Feb 10 | Yet more DP: Matrix chain multiplication ● Subset-Sum and pseudopolynomial time | [KT 6.4]; [Eri 3.8]; [CLRS 14.2] (notes) |
| 12 |
Thu Feb 12 | DP and graph algorithms ● Bellman-Ford SSSP ● Floyd-Warshall APSP | [KT 6.8]; [Eri 8.7, 9.8]; [CLRS 22.1—2, 23.1—2] (notes) |
| X |
Fri Feb 13 | Problem solving session (optional extended session until 17:30) | |
| S |
Mon Feb 16 | Homework 6 due by 22:00 | |
| 13 |
Tue Feb 17 | 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) |
| 14 |
Thu Feb 19 | 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] |
| X |
Fri Feb 20 | Problem solving session (optional extended session until 17:30) | |
| S |
Mon Feb 23 | Homework 7 due by 22:00 | |
| 15 |
Tue Feb 24 | Kruskal's algorithm ● Union-Find | [KT 4.5]; [CLRS Ch 21]; [Eri 7.5] |
| Q |
Wed Feb 25 | **Midterm 2** from 18:30 to 21:30 in Cummings 200 | |
| 16 |
Thu Feb 26 | Flows and cuts I ● Max-flow min-cut theorm | [Eri Ch 10] |
| X |
Fri Feb 27 | (X-hour not used) | |
| S |
Mon Mar 02 | Homework 8 due by 22:00 | |
| 17 |
Tue Mar 03 | Flows and cuts II ● Efficient algorithms (outline) ● Algorithmic applications of max-flow | [Eri Ch 10, 11] (notes) |
| 18 |
Thu Mar 05 | Flows and cuts III ● Further applications | [Eri Ch 11] (notes) |
| X |
Fri Mar 06 | Problem solving session (optional extended session until 17:30) | |
| S |
Mon Mar 09 | Homework 9 due by 22:00 | |
| 19 |
Tue Mar 10 | Introduction to NP-completeness ● Reductions | [Eri Ch 12] excerpts |
As you can see, we will use every X-hour. When there is no lecture in the x-hour, we will use it as a problem-solving session, where students can have staff-guided practice solving non-homework problems from the problem sets. We have the classroom available until 17:30 (i.e., one-hour beyond the end of the X-hour). Attending the extended session (beyond the X-hour) is optional.
The **final exam** has been scheduled by the Registrar's Office:
15:00 to 18:00 on Mon Mar 16, in MacLean MB01.
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.