| 1/9 | Read Chapter 0
Watch Big Oh Notation (Tim Roughgarden) Introduction to the course |
| 1/11 | Read Section 1.1
Watch Integer Multiplication (Tim Roughgarden) Bitwise arithmetic |
| 1/16 | MLK Day (no class) |
| 1/18 | Read Section 1.2
Watch RA1: Modular Arithmetic (Eric Vigoda) Modular arithmetic |
| 1/23 | Read Sections 1.3-1.4
Watch RA2: RSA (Eric Vigoda) and RSA-129 (Ron Rivest) Primality and RSA encryption Quiz 1 |
| 1/25 | Read Section 1.5
Universal hashing Homework 1 due |
| 1/30 | Read Sections 2.1 and 2.2
Watch Karatsuba Multiplication (Tim Roughgarden) Integer multiplication and Master theorem |
| 2/1 | Read Sections 2.3 and 2.5
Watch Strassen's Subcubic Matrix Multiplication (Tim Roughgarden) Mergesort and matrix multiplication |
| 2/6 | Read Section 2.4
Watch Randomized Selection (Tim Roughgarden) Median/Select Quiz 2 |
| 2/8 | Read Section 2.6
Fast Fourier transform (FFT) Homework 2 due |
| 2/13 | Read Section 3.1
Watch Graph Representations (Tim Roughgarden) Graphs |
| 2/15 | Read Sections 3.2-3.4
Watch DFS The Basics (Tim Roughgarden) Depth-first search (DFS) and strongly connected components |
| 2/20 | Read Sections 4.1-4.3
Watch BFS The Basics (Tim Roughgarden) Breadth-first search (BFS) Quiz 3 |
| 2/22 | Read Sections 4.4-4.7
Watch Dijkstra's Algorithm Examples (Tim Roughgarden) Shortest paths algorithms Homework 3 due |
| 2/27 | Read Section 5.1
Watch Greedy Algorithms and MST (Charles Leiserson) Minimum spanning tree (MST) |
| 3/1 | Read Sections 5.3-5.4
Other greedy algorithms: Horn formulas and approximate set cover |
| 3/13 | Read Sections 6.1-6.2
Watch Dynamic Programming and Longest Common Subsequence (Charles Leiserson) Elements of DP and Longest Increasing Subsequence |
| 3/15 | Read Section 6.3
Watch videos 2-12 of Algorithms@Udacity (Charles Brubaker) Edit Distance and Longest Common Subsequence |
| 3/20 | Read Section 6.4
Watch DP2: Knapsack (Eric Vagoda) Knapsack Project proposals due Quiz 4 |
| 3/22 | Read Section 6.6
All-Pairs Shortest Paths Homework 4 due |
We will be using alternate materials for this section:
Chapter 27 of Introduction to Algorithms by Cormen, Leiserson, Rivest, and Stein
| 3/27 | Read Section 27.1 of CLRS
Watch Multithreaded Programming (Charles Leiserson) PRAM model, performance measures, and thread scheduling |
| 3/29 | Read Section 27.2 and 27.3 of CLRS
Watch Multithreaded Algorithms (Charles Leiserson) Parallel matrix multiplication and mergesort |
| 4/3 | Parallel dynamic programming
Quiz 5 |
| 4/5 | Read Sections 7.1 and 7.6
Digression: Linear programming and simplex Homework 5 due |
| 4/10 | Read Sections 8.1-8.2
Watch NP1: Definitions (Eric Vagoda) P vs NP and NP-complete problems |
| 4/12 | Read Section 8.3
Watch NP2: 3SAT (Eric Vagoda) Reductions |
| 4/17 | Reductions continued
Quiz 6 |
| 4/19 | Read Section 9.1
Backtracking and branch-and-bound Homework 6 due |
| 4/24 | Read Section 9.2
Approximation algorithms |
| 4/26 | Read Section 9.3
Local search heuristics |
| 5/3 | Project presentations (2pm) |