| WEEK |
DAY |
ANNOUNCEMENTS |
TOPIC & READING |
LAB |
| 1 |
Sep 02 |
|
Course Introduction
Stable Matching
K&T Ch1 |
Lab 1
Homework 1 |
| Sep 04 |
|
| Sep 06 |
|
| 2 |
Sep 09 |
|
Analysis
Graph Algorithms Intro
K&T Ch 2.1-2.4, 3.1-3.2 |
Lab 2
Homework 2 |
| Sep 11 |
|
| Sep 13 |
Drop/Add ends |
| 3 |
Sep 16 |
|
Graph Algorithms
K&T Ch 3 |
Lab 3
Homework 3
Solutions to HW3 |
| Sep 18 |
|
| Sep 20 |
|
| 4 |
Sep 23 |
|
Directed Graphs
K&T 3.6 |
Lab 4
Homework 4 |
| Sep 25 |
|
Greedy Algorithms
K&T Ch 4 |
| Sep 27 |
|
| 5 |
Sep 30 |
|
Problem Set Review |
Lab 5 |
| Oct 02 |
|
Greedy Algorithms (continued) |
| Oct 04 |
|
Union Find/Divide and Conquer
K&T Ch 5-5.2 |
| 6 |
Oct 07 |
|
Divide and Conquer (continued) K&T Ch 5.3-5.5 |
Lab 6
Lab 6 Solution Set
Homework 5 |
| Oct 09 |
|
| Oct 11 |
|
| |
Oct 14 |
Fall break |
Oct 16 |
Oct 18 |
| 7 |
Oct 21 |
|
Dynamic Programming
K&T Ch 6 |
Lab 7 |
| Oct 23 |
|
| Oct 25 |
|
| 8 |
Oct 28 |
|
Intractability
K&T 8.1-8.4
See also CLRS Ch 34
Midterm |
Lab 8
Homework 6 |
| Oct 30 |
|
| Nov 01 |
|
| 9 |
Nov 04 |
|
Approximation Algorithms
K&T 11.1-11.4, 11.6, 11.8
See also CLRS Ch 35 |
Lab 9
Homework 7 |
| Nov 06 |
|
| Nov 08 |
Last day to declare CR/NC or withdraw with a "W"
|
| 10 |
Nov 11 |
|
Randomized Algorithms
K&T 13.1-13.5 |
Lab 10
Homework 8 |
| Nov 13 |
|
| Nov 15 |
|
| 11 |
Nov 18 |
|
Streaming Algorithms
The Space Complexity of Approximating The Frequency Moments, by Alon, Matias, Szegedy STOC 1996. |
|
| Nov 20 |
|
| Nov 22 |
|
| 12 |
Nov 25 |
|
Alternate Models of Computation
CLRS 18 |
Homework 9 |
| Nov 27 |
|
Nov 29 |
Thanksgiving |
| 13 |
Dec 02 |
|
Alternate Models of Computation
CLRS 18 (continued) |
| Dec 04 |
|
Parallel Algorithms |
Lab 12 |
| Dec 06 |
|
| 14 |
Dec 09 |
|
Class Review |
|
| Dec 11 |
|
|
|