| 1/13 | Read Chapter 0
Watch Big Oh Notation (Tim Roughgarden) Introduction to the course |
| 1/15 | Read Section 1.1
Watch Integer Multiplication (Tim Roughgarden) Integer arithmetic |
| 1/17 | Read Section 1.2
Watch videos 2-22 of RA1: Modular Arithmetic (Eric Vigoda) Modular arithmetic |
| 1/20 | MLK Day: No class |
| 1/22 | Read Section 1.3
Watch videos 1-23 of RA2: RSA (Eric Vigoda) Primality testing Homework 1 due |
| 1/24 | Read Section 1.4
Watch RSA-129 (Ron Rivest) RSA encryption Quiz 1 |
| 1/27 | Read Section 2.1
Watch Karatsuba Multiplication (Tim Roughgarden) Integer multiplication |
| 1/29 | Read Section 2.2
Master theorem Homework 2 due |
| 1/31 | Read Section 2.3
Mergesort |
| 2/3 | Read Section 2.4
Watch Randomized Selection (Tim Roughgarden) Median/Select |
| 2/5 | Read Selection (Avrim Blum)
Watch videos 1-15 of DC2: Linear-Time Median (Eric Vigoda) Deterministic Selection Homework 3 due |
| 2/7 | Read Section 2.5
Watch Strassen's Subcubic Matrix Multiplication (Tim Roughgarden) Matrix multiplication Quiz 2 |
| 2/10 | Read Section 3.1
Watch Graph Representations (Tim Roughgarden) Graphs |
| 2/12 | Read Sections 3.2-3.3
Depth-first search (DFS) Programming Assignment 1a due |
| 2/14 | (Optional) Work on PA 1b |
| 2/17 | Read Sections 4.1-4.2
Breadth-first search (BFS) |
| 2/19 | Read Section 4.3
Finish BFS Programming Assignment 1b due |
| 2/21 | Read Section 4.4
Watch Dijkstra's Algorithm Examples (Tim Roughgarden) Dijkstra's Algorithm Quiz 3 |
| 2/24 | Read Sections 5.1.1-5.1.2
Watch Greedy Algorithms and MST (Charles Leiserson) Minimum spanning tree (MST) and cut property |
| 2/26 | Read Sections 5.1.3 and 5.1.5
Algorithms for MST Homework 4 due |
| 2/28 | Read Section 5.1.4
A data structure for disjoint sets |
| 3/2 | Read Section 5.4
Approximate set cover |
| 3/4 | Midterm Review |
| 3/6 | IN-CLASS MIDTERM |
| 3/9 | Spring Break: No class |
| 3/11 | Spring Break: No class |
| 3/13 | Spring Break: No class |
| 3/16 | Canceled due to COVID-19: No class |
| 3/18 | Canceled due to COVID-19: No class |
| 3/20 | Canceled due to COVID-19: No class |
| 3/23 | Read Sections 6.1-6.2
Watch Dynamic Programming and Longest Common Subsequence (Charles Leiserson) Elements of DP and Longest Increasing Subsequence |
| 3/25 | Read Section 6.3
Watch videos 2-12 of Algorithms@Udacity (Charles Brubaker) Edit Distance |
| 3/27 | Read Section 6.4
Watch videos 1-16 of DP2: Knapsack, Chain Multiply (Eric Vagoda) Knapsack |
| 3/30 | Dynamic Programming Catch up |
We will be using alternate materials for this section:
Chapter 27 of Introduction to Algorithms by Cormen, Leiserson, Rivest, and Stein
| 4/1 | Read Section 27.1 of CLRS
Watch Multithreaded Programming (Charles Leiserson) PRAM model, performance measures, and thread scheduling Programming Assignment 2a due |
| 4/3 | Read Section 27.2 of CLRS
Watch Multithreaded Algorithms (Charles Leiserson) Analyzing parallel algorithms: matrix multiplication |
| 4/6 | Read Section 27.3 of CLRS
Analyzing parallel algorithms: merge sort |
| 4/8 | Parallel dynamic programming
Programming Assignment 2b due |
| 4/10 | Good Friday: No class |
| 4/13 | Read Sections 8.1-8.2
Watch videos 1-12, 8-21 of NP1: Definitions (Eric Vagoda) P vs NP and NP-complete problems |
| 4/15 | Watch videos 22-27 of NP1: Definitions (Eric Vagoda) Satisfiability and other search problems Homework 5 due |
| 4/17 | Read Section 8.3
Watch videos 1-16 of NP2: 3SAT (Eric Vagoda) Reductions |
| 4/20 | Watch videos 1-11 of NP3: Graph Problems (Eric Vagoda) Reductions (continued) |
| 4/22 | Read Section 9.1
Coping with NP-completeness Homework 6 due |
| 4/24 | Backtracking and branch-and-bound |
| 4/27 | Read Section 9.2
Approximation algorithms |
| 4/29 | Final Review (last day of class) |
| 5/1 | FINAL EXAM (2pm) |