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) |