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