| 8/28 | Introduction to the course |
| 8/30 | Read Chapter 0
Review of asymptotic notation |
| 9/1 | Read Section 1.1
Integer arithmetic |
| 9/4 | Read Section 1.2
Modular arithmetic |
| 9/6 | Read Section 1.3
Primality testing |
| 9/8 | Read Section 1.4
RSA encryption Programming Assignment 1a due |
| 9/11 | Read Section 2.1
Integer multiplication |
| 9/13 | Read Section 2.2
Master theorem |
| 9/15 | Read Section 2.3
Mergesort Programming Assignment 1b due |
| 9/18 | Read Section 2.4
Medians |
| 9/20 | Read Section 2.5
Matrix multiplication Quiz 1 |
| 9/22 | Fast matrix multiplication
Homework 1 due |
| 9/25 | Read Section 3.1
Graphs |
| 9/27 | Read Sections 3.2-3.3
Depth-first search (DFS) |
| 9/29 | Algorithms using DFS
Programming Assignment 2a due |
| 10/2 | Read Sections 4.1-4.2
Breadth-first search (BFS) |
| 10/4 | Read Sections 4.3-4.4
Dijkstra's Algorithm Quiz 2 |
| 10/6 | Read Section 4.6
Bellman-Ford Algorithm Programming Assignment 2b due |
| 10/9 | Read Sections 5.1.1-5.1.2
Minimum spanning tree (MST) and cut property |
| 10/11 | Read Sections 5.1.3 and 5.1.5
Algorithms for MST |
| 10/13 | Fall Break |
| 10/16 | Read Section 5.4
Approximate set cover Homework 2 due |
| 10/18 | Midterm review |
| 10/20 | IN-CLASS MIDTERM |
| 10/23 | Read Sections 6.1-6.2
Elements of DP and Longest Increasing Subsequence |
| 10/25 | Read Section 6.3
Edit Distance |
| 10/27 | Longest Common Subsequence |
| 10/30 | Read Section 6.4
Knapsack Homework 3 due |
| 11/1 | Catch-up day
Quiz 3 |
| 11/3 | Read Section 6.5
Chain Matrix Multiplication Programming Assignment 3a due |
We will be using an alternate textbook for this section: CLRS - Chapter 27
| 11/6 | Read pg. 772 -- 783
Parallel Random Access Machine model |
| 11/8 | Read pg. 784 -- 790
Analyzing multithreaded algorithms |
| 11/10 | Read Section 27.2
Multithreaded matrix multiplication |
| 11/13 | Read Section 27.3
Multithreaded mergesort Programming Assignment 3b due |
| 11/15 | Floyd-Warshall and multithreaded all-pairs shortest paths
Quiz 4 |
| 11/17 | Memory models and data movement |
| 11/20 | Read Sections 8.1-8.2
P vs NP and NP-complete problems Homework 4 Due |
| 11/22 | Thanksgiving Break |
| 11/24 | Thanksgiving Break |
| 11/27 | Satisfiability and other search problems |
| 11/29 | Read Section 8.3
Reductions |
| 12/1 | Reductions (continued)
Homework 5 Due |
| 12/4 | Read Section 9.1
Coping with NP-completeness |
| 12/6 | Read Section 9.2
Approximation algorithms |
| 12/8 | Final Review (last day of class)
Homework 6 Due |
| 12/14 | FINAL EXAM (2pm) |