Any content that's colored light gray is tentative and subject to change.
Lectures and Exams
Our lectures will be in the two long sessions on Tuesday and Thursday mornings. Each long session will have a five-minute break about one hour from the start. In the table below, I have provided references to relevant sections of 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. Remember that you don't need to be reading all three books; pick the one whose style you like best.
For topics where I'm not satisfied with the presentation in these reference books, I shall be providing lecture notes written by myself. Pay extra attention to these notes and study them carefully.
We will use every x-hour and have a short quiz (15 or 20 minutes) to test your engagement in the lectures and basic understanding. These quizzes will be designed to be very basic and will not ask trick question, nor expect you to write long answers or solve complicated problems.
| # | Date | Class Topics / Other Events | References |
|---|---|---|---|
| 1 |
Tue Sep 15 | Analyzing time complexity ● What is a unit cost operation? ● Binary search ● List vs array ● Proofs using loop invariants | [KT 2.1]; [CLRS 2.1, 2.2]; [Eri Ch 0] |
| 2 |
Thu Sep 17 | Asymptotic notation: O, Ω, Θ ● Loops invariants revisited ● Recursion | [CLRS Ch 2]; [Eri 1.1—1.6] (notes) |
| X |
Fri Sep 18 | Administrivia ● How to succeed in this course ● Quiz 1 | course website and canvas |
| 3 |
Tue Sep 22 | Efficient sorting ● InsertionSort and MergeSort ● QuickSort and HeapSort | |
| 4 |
Thu Sep 24 | Graphs and digraphs ● Adjacency list/matrix ● Graph traversal and its properties ● Breadth-first search | |
| X |
Fri Sep 25 | Quiz 2 | |
| 5 |
Tue Sep 29 | Depth-first search ● Parenthesis theorem and white-path theorem ● DAGs and Cycle finding | |
| 6 |
Thu Oct 01 | Topological sort ● Strongly connected components | |
| X |
Fri Oct 02 | Quiz 3 | |
| 7 |
Tue Oct 06 | Divide-and-conquer ● MergeSort redux ● Counting inversions ● Karatsuba integer multiplication ● Strassen matrix multiplication | |
| 8 |
Thu Oct 08 | Master theorem/method for recurrences ● Closest pair of points ● Selection in linear time | |
| X |
Fri Oct 09 | Quiz 4 | |
| 9 |
Tue Oct 13 | Dynamic programming: Fibonacci numbers, Rod cutting | |
| Q |
Wed Oct 14 | **Midterm 1** from 18:30 to 21:30 in Cummings 200 | |
| 10 |
Thu Oct 15 | Systematically presenting a DP algorithm ● Weighted interval scheduling ● Longest common subsequence | |
| X |
Fri Oct 16 | Quiz 5 | |
| 11 |
Tue Oct 20 | Yet more DP: Matrix chain multiplication ● Subset-Sum and pseudopolynomial time | |
| 12 |
Thu Oct 22 | DP and graph algorithms ● Bellman-Ford SSSP ● Floyd-Warshall APSP | |
| X |
Fri Oct 23 | Quiz 6 | |
| 13 |
Tue Oct 27 | Generic relaxation-based SSSP algorithms ● Correctness of Bellman-Ford algorithm ● Dijkstra's algorithm and its correctness | |
| 14 |
Thu Oct 29 | Minimum spanning trees and Prim's algorithm ● Cut property and correctness of Prim ● Priority queues and time complexity | |
| X |
Fri Oct 30 | Quiz 7 | |
| 15 |
Tue Nov 03 | Kruskal's algorithm ● Union-Find | |
| Q |
Wed Nov 04 | **Midterm 2** from 18:30 to 21:30 in Cummings 200 | |
| 16 |
Thu Nov 05 | Flows and cuts I ● Max-flow min-cut theorm | |
| X |
Fri Nov 06 | Quiz 8 | |
| 17 |
Tue Nov 10 | Flows and cuts II ● Efficient algorithms (outline) ● Algorithmic applications of max-flow | |
| 18 |
Thu Nov 12 | Flows and cuts III ● Further applications | |
| X |
Fri Nov 13 | Quiz 9 | |
| 19 |
Tue Nov 17 | Introduction to NP-completeness ● Reductions |
The **final exam** has been scheduled by the Registrar's Office:
11:30 to 14:30 on Sun Nov 22, in Location TBD.
Homework
We will have nine problem sets, corresponding to the nine weeks of the term. Each problem set will have some designated "homework problems", perhaps an "extra-credit problem", and some "further practice problems". There is homework associated with every class, which consists of
- reading any one of the reference book sections listed, plus any slides or notes linked from the table above;
- thinking about and writing up solutions to the associated homework problems.
Homework will be graded mostly for effort and completion. This works as follows.
- You will be assigned to a section, led by one of our section leaders, meeting at a designated time each week. Your attendance at this meeting is mandatory. At the meeting, you will interact with your section leader to convince them that you have engaged with the week's homework problems to a satisfactory level. If so, the section leader will mark the relevant homework problems as "done" and that will count towards your homework grade.
- It is important to learn to write well, including rigorous proofs, and you are strongly encouraged to do so on every homework problem you solve. However, your homework grade will not depend on your writeup being flawless.