| 1/10 | Introduction to the course, computing Fibonacci numbers, review of big Oh notation |
| 1/12 | Read Sections 1.1 and 1.2 Modular arithmetic Programming Assignment 1 posted on Sakai |
| 1/17 | Read Section 1.3 Primality testing |
| 1/19 | Read Section 1.4 Cryptography and RSA |
| 1/24 | Finish up RSA |
| 1/26 | Read Sections 2.1-2.2
Multiplication and recurrence relations Programming Assignment 1 Due |
| 1/31 | Read Sections 2.3-2.4 Mergesort and medians |
| 2/2 | Read Section 2.5
Matrix multiplication Quiz 1 in class |
| 2/7 | Read Sections 3.1-3.3 Graphs and DFS |
| 2/9 | Algorithms using DFS Homework 1 Due |
| 2/14 | Read Sections 4.1-4.2 DFS and BFS |
| 2/16 | Read Section 4.3-4.4
Dijkstra's Algorithm Quiz 2 in class |
| 2/21 | Read Section 5.1
Minimum Spanning Tree |
| 2/23 | Read Section 5.4
Set Cover Programming Assignment 2 Due |
| 2/28 | Midterm Review |
| 3/2 | IN-CLASS MIDTERM |
| 3/7 | Spring Break |
| 3/9 | Spring Break |
| 3/14 | Read Sections 6.1-6.2
Elements of DP and Longest Increasing Subsequence |
| 3/16 | Read Section 6.3
Edit Distance and Longest Common Subsequence Quiz 3 in class |
| 3/21 | Read Sections 6.4-6.5
Knapsack and Chain Matrix Multiplication |
| 3/23 | Read Section 6.6
Floyd-Warshall - All-Pairs Shortest Paths Homework 2 Due 3/24 |
We will be using an alternate textbook for this section: CLRS - Chapter 27
| 3/28 | Read Section 27.1
Parallel Random Access Machine model |
| 3/30 | Read Section 27.2
Multithreaded matrix multiplication Quiz 4 in class |
| 4/4 | Read Section 27.3
Multithreaded mergesort |
| 4/6 | Memory models and data movement
Programming Assignment 3 Due |
| 4/11 | Read Sections 8.1-8.2
P vs NP and NP-complete problems |
| 4/13 | Read Section 8.3
Reductions Quiz 5 in class |
| 4/18 | Read Section 9.1
Coping with NP-completeness |
| 4/20 | Read Section 9.2
Approximation algorithms Homework 3 Due |
| 4/25 | Final Review (last day of class) |
| 4/29 | FINAL EXAM (9am) |