This page is retained for archival purposes. The links to materials in the schedule table will not work.
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 Mar 28 | 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] (slides) |
| 2 |
Wed Mar 29 | (x-hour) Administrivia ● How to succeed in this course | course website and canvas (board) |
| 3 |
Thu Mar 30 | Asymptotic notation: O, Ω, Θ ● Proving algorithm correctness using invariants ● Recursion | [CLRS Ch 2]; [Eri 1.1—1.6] (board) |
| S |
Mon Apr 03 | Homework 1 due by 22:00 | |
| 4 |
Tue Apr 04 | 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) (board) |
| 5 |
Wed Apr 05 | (x-hour) Graphs and digraphs ● Adjacency list ● Adjacency matrix | [CLRS 20.1]; [KT 3.1, 3.3]; [Eri 5.1—5.4] (board) |
| 6 |
Thu Apr 06 | Breadth-first search ● Shortest paths (unweighted) | [CLRS 20.2]; [KT 3.1—3.3]; [Eri Ch 5] (notes) (board) |
| S |
Mon Apr 10 | Homework 2 due by 22:00 | |
| 7 |
Tue Apr 11 | Depth-first search ● Parenthesis theorem and Path lemma ● DAGs and Cycle finding | [Eri 6.1, 6.2]; [KT 3.3—3.6]; [CLRS 20.3, 20.4] (board) |
| X |
Wed Apr 12 | (x-hour) used as extra office hours | |
| 8 |
Thu Apr 13 | Topological sort ● Strongly connected components | [Eri 6.3, 6.5, 6.6]; [CLRS 20.4, 20.5] (board) |
| S |
Mon Apr 17 | Homework 3 due by 22:00 | |
| 9 |
Tue Apr 18 | Divide-and-conquer ● MergeSort redux ● Counting inversions ● Karatsuba integer multiplication | [KT 5.1—5.3, 5.5]; [Eri 1.7, 1.9]; [CLRS Ch 4] (board) |
| X |
Wed Apr 19 | x-hour not used | |
| 10 |
Thu Apr 20 | Strassen matrix multiplication ● Closest pair of points ● Selection in linear time | [Eri 1.8]; [CLRS 9.1, 9.3] (board) |
| S |
Mon Apr 24 | Homework 4 due by 22:00 | |
| 11 |
Tue Apr 25 | Analysis of linear-time selection ● Dynamic programming: Fibonacci numbers, Rod cutting | [Eri 3.1—3.5]; [CLRS 14.1] (board) |
| Q |
Wed Apr 26 | **Midterm 1** from 17:30 to 20:30 | |
| 12 |
Thu Apr 27 | Systematically presenting a DP algorithm ● Weighted interval scheduling ● Longest common subsequence ● Matrix chain multiplication | [KT 6.1, 6.2]; [CLRS 14.2—14.4] (notes) (board) |
| S |
Mon May 01 | Homework 5 due by 22:00 | |
| 13 |
Tue May 02 | DP and graph algorithms ● Bellman-Ford SSSP ● Floyd-Warshall APSP | [Eri 8.7, 9.8] (board) |
| X |
Wed May 03 | x-hour not used | |
| 14 |
Thu May 04 | Floyd-Warshall revisited ● Subset-Sum and pseudopolynomial time ● DP wrap-up | [KT 6.4]; [Eri 3.8] (notes) (board) |
| S |
Mon May 08 | Homework 6 due by 22:00 | |
| 15 |
Tue May 09 | 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] (board) |
| 16 |
Wed May 10 | (x-hr) Minimum spanning trees and Prim's algorithm | [KT 4.5]; [CLRS Ch 21; [Eri 7.1—7.4] (board) |
| 17 |
Thu May 11 | Priority queues ● Time complexity of Dijkstra and Prim ● Cut property and correctness of Prim | [KT 4.5]; [CLRS Ch 21; [Eri 7.1—7.4] (board) |
| S |
Mon May 15 | Homework 7 due by 22:00 | |
| 18 |
Tue May 16 | Randomized algorithms; QuickSelect and QuickSort | [KT 13.12, 13.5] (notes) (board) |
| Q |
Wed May 17 | **Midterm 2** from 17:30 to 20:30 | |
| 19 |
Thu May 18 | Hash functions; hash tables; closest-pair redux | [KT 13.6, 13.7] (board) |
| S |
Mon May 22 | Homework 8 due by 22:00 | |
| 20 |
Tue May 23 | Flows and cuts I | [Eri Ch 10] (board) |
| X |
Wed May 24 | x-hour not used | |
| 21 |
Thu May 25 | Flows and cuts II | [Eri Ch 11] (board) |
| S |
Mon May 29 | Homework 9 due by 22:00 | |
| 22 |
Tue May 30 | Tying up loose ends; Wrap-up | (no refs) (board) |
The **final exam** has been scheduled by the Registrar's Office:
8:00 to 11:00 on Sat Jun 03, in Spanos Auditorium (Cummings 100).
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.