| 8/24 | Read Chapter 0
Watch Big Oh Notation (Tim Roughgarden) Introduction to the course |
| 8/26 | Read Sections 1.1-1.2
Watch Integer Multiplication (Tim Roughgarden) and RA1: Modular Arithmetic (Eric Vigoda) Bitwise arithmetic |
| 8/31 | Read Section 1.3
Watch RA2: RSA (Eric Vigoda) Primality Homework 1 due |
| 9/2 | Read Section 1.4
Watch RSA-129 (Ron Rivest) RSA encryption Quiz 1 |
| 9/7 | Read Section 2.1
Watch Karatsuba Multiplication (Tim Roughgarden) Integer multiplication |
| 9/9 | Read Section 2.2
Master theorem Homework 2 due |
| 9/14 | Read Sections 2.3-2.4
Watch Randomized Selection (Tim Roughgarden) Mergesort and Median/Select Quiz 2 |
| 9/16 | Read Section 2.5
Watch Strassen's Subcubic Matrix Multiplication (Tim Roughgarden) Matrix multiplication Homework 3 due |
| 9/21 | Read Section 3.1
Watch Graph Representations (Tim Roughgarden) Graphs |
| 9/23 | Read Sections 3.2-3.3
Watch DFS The Basics (Tim Roughgarden) Depth-first search (DFS) Homework 4 due |
| 9/28 | Read Sections 4.1-4.3
Watch BFS The Basics (Tim Roughgarden) Breadth-first search (BFS) Quiz 3 |
| 9/30 | Read Sections 4.4-4.6
Watch Dijkstra's Algorithm Examples (Tim Roughgarden) Dijkstra's and Bellman-Ford Algorithms Homework 5 due |
| 10/5 | IN-CLASS MIDTERM |
| 10/7 | Fall Break (no class) |
| 10/12 | Read Section 5.1
Watch Greedy Algorithms and MST (Charles Leiserson) Minimum spanning tree (MST) |
| 10/14 | Read Section 5.4
Approximate set cover |
| 10/19 | Read Sections 6.1-6.2
Watch Dynamic Programming and Longest Common Subsequence (Charles Leiserson) Elements of DP and Longest Increasing Subsequence |
| 10/21 | Read Section 6.3
Watch videos 2-12 of Algorithms@Udacity (Charles Brubaker) Edit Distance and Longest Common Subsequence Homework 6 due |
| 10/26 | Read Section 6.4
Watch DP2: Knapsack (Eric Vagoda) Knapsack |
| 10/28 | Read Section 6.6
All-Pairs Shortest Paths Quiz 4 Homework 7 due |
We will be using alternate materials for this section:
Chapter 27 of Introduction to Algorithms by Cormen, Leiserson, Rivest, and Stein
| 11/2 | Read Section 27.1 of CLRS
Watch Multithreaded Programming (Charles Leiserson) PRAM model, performance measures, and thread scheduling |
| 11/4 | Read Section 27.2 of CLRS
Watch Multithreaded Algorithms (Charles Leiserson) Parallel matrix multiplication Homework 8 due |
| 11/9 | Read Section 27.3 of CLRS
Parallel merge sort Quiz 5 |
| 11/11 | Parallel dynamic programming |
| 11/16 | Read Sections 8.1-8.2
Watch NP1: Definitions (Eric Vagoda) P vs NP and NP-complete problems Homework 9 due |
| 11/18 | Read Section 8.3
Watch NP2: 3SAT (Eric Vagoda) Reductions Quiz 6 |
| 11/23 | Read Section 9.1
Backtracking and branch-and-bound Homework 10 due |
| 11/25 | Thanksgiving Break (no class) |
| 11/30 | Read Section 9.2
Approximation algorithms |
| 12/2 | Final Review (last day of class) |
| 12/6 | FINAL EXAM (9am) |