| 1/14 | Introduction to the course |
| 1/16 | Read Chapter 0 and Section 1.1
Review of asymptotic notation and integer arithmetic |
| 1/18 | Finish integer arithmetic |
| 1/21 | MLK Day: No class |
| 1/23 | Read Section 1.2
Modular arithmetic |
| 1/25 | Read Section 1.3
Primality testing |
| 1/28 | Read Section 1.4
RSA encryption Programming Assignment 1a due |
| 1/30 | Read Section 2.1
Integer multiplication |
| 2/1 | Read Section 2.2
Master theorem Quiz 1 |
| 2/4 | Read Section 2.3
Mergesort Programming Assignment 1b due |
| 2/6 | Read Section 2.4
Medians |
| 2/8 | Read Section 2.5
Matrix multiplication Homework 1 due |
| 2/11 | Read Section 3.1
Graphs |
| 2/13 | Read Sections 3.2-3.3
Depth-first search (DFS) |
| 2/15 | Algorithms using DFS
Programming Assignment 2a due |
| 2/18 | Read Sections 4.1-4.2
Breadth-first search (BFS) |
| 2/20 | Read Sections 4.3-4.4
Dijkstra's Algorithm Quiz 2 |
| 2/22 | Read Section 4.6
Bellman-Ford Algorithm Programming Assignment 2b due |
| 2/25 | Midterm review |
| 2/27 | IN-CLASS MIDTERM |
| 3/1 | No class |
| 3/4 | Read Sections 5.1.1-5.1.2
Minimum spanning tree (MST) and cut property |
| 3/6 | Read Sections 5.1.3 and 5.1.5
Algorithms for MST |
| 3/8 | Read Section 5.4
Approximate set cover Homework 2 due |
| 3/11 | Spring Break: No class |
| 3/13 | Spring Break: No class |
| 3/15 | Spring Break: No class |
| 3/18 | Read Sections 6.1-6.2
Elements of DP and Longest Increasing Subsequence |
| 3/20 | Read Section 6.3
Edit Distance |
| 3/22 | Longest Common Subsequence |
| 3/25 | Read Section 6.4
Knapsack Homework 3 due |
| 3/27 | Read Section 6.5
Chain Matrix Multiplication Quiz 3 |
| 3/29 | Catch-up day
Programming Assignment 3a due |
We will be using alternate materials for this section:
Minicourse on Multithreaded Programming
Lecture 1 (Leiserson)
Lecture 2 (Leiserson)
| 4/1 | Read Section 1 of Minicourse
PRAM model, performance measures, and thread scheduling |
| 4/3 | Read Section 2 of Minicourse
Analyzing parallel algorithms: matrix multiplication |
| 4/5 | Analyzing parallel algorithms: merge sort |
| 4/8 | Review of matrix multiplication and merge sort
Programming Assignment 3b due |
| 4/10 | Floyd-Warshall and multithreaded all-pairs shortest paths |
| 4/12 | Memory models and data movement |
| 4/15 | Read Sections 8.1-8.2
P vs NP and NP-complete problems Homework 4 Due |
| 4/17 | Satisfiability and other search problems
Quiz 4 |
| 4/19 | Good Friday: No class |
| 4/22 | Read Section 8.3
Reductions |
| 4/24 | Reductions (continued) |
| 4/26 | Read Section 9.1
Coping with NP-completeness |
| 4/29 | Backtracking and branch-and-bound
Homework 5 Due |
| 5/1 | Final Review (last day of class) |
| 5/8 | FINAL EXAM (2pm) |