| WEEK |
DATE |
ANNOUNCEMENTS |
TOPIC & READING |
LAB |
| 1 | Aug 29 | | Course Introduction
Stable Matching
K&T Ch1 | Lab 1
Homework 1 |
Aug 31 | |
Sep 02 | |
| 2 | Sep 05 | | Analysis
K&T Ch 2.1-2.2 | Lab 2
Homework 2 |
Sep 07 | | Analysis (continued)
K&T Ch 2.3 |
Sep 09 | Drop/Add ends | Analysis (continued)
K&T Ch 2.4 |
| 3 | Sep 12 | | Graph Algorithms
K&T Ch 3.1-3.2 | Lab 3
Homework 3 |
Sep 14 | | Graph Algorithms (continued)
K&T Ch 3.4 |
Sep 16 | | Graph Algorithms (continued)
K&T Ch 3.5-3.6 |
| 4 | Sep 19 | | Graph Algorithms (continued) | Lab 4
Homework 4 |
Sep 21 | | Greedy Algorithms
K&T Ch 4.1-4.2, 4.4-4.5 |
Sep 23 | |
| 5 | Sep 26 | | Greedy Algorithms (continued)
K&T Ch 4.2, 4.4-4.5 | Lab 5
Homework 5 |
Sep 28 | | Divide and Conquer
K&T Ch 5 |
Sep 30 | |
| 6 | Oct 03 | no class -- Rosh Hashanah | Divide and Conquer (continued)
K&T Ch 5 | Lab 6 |
Oct 05 | |
Oct 07 | |
| | Oct 10 | Fall Break |
Oct 12 |
Oct 14 |
| 7 | Oct 17 | | Dynamic Programming
K&T Ch 6.1, 6.4 | Homework 6 |
Oct 19 | Midterm |
Oct 21 | | Dynamic Programming (continued)
K&T Ch 6.5 |
| 8 | Oct 24 | | Dynamic Programming (continued)
K&T Ch 6.2 | Lab 8
Homework 7 |
Oct 26 | | Intractability
K&T 8.1-8.4
See also CLRS Ch 34 |
Oct 28 | |
| 9 | Oct 31 | | Intractability (continued) | Lab 9
Homework 8 |
Nov 02 | | A Brief History of Theoretical Computer Science |
Nov 04 | Last day to declare CR/NC or
withdraw with a "W" | Approximation Algorithms |
| 10 | Nov 07 | | Approximation Algorithms
K&T 11.1-11.4, 11.6, 11.8
See also CLRS Ch 35 | Lab 10
Homework 9 |
Nov 09 | |
Nov 11 | |
| 11 | Nov 14 | | Randomized Algorithms
K&T 13.1-13.5 | Lab 11
Homework 10 |
Nov 16 | |
Nov 18 | |
| 12 | Nov 21 | | Lower Bounds |
|
Nov 23 | |
Nov 25 | Thanksgiving Break |
| 13 | Nov 28 | | Alternate Models of Computation: Quantum Computing | Lab 13
Homework 11 |
Nov 30 | |
Dec 02 | |
| 14 | Dec 05 | | Class review |
|