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.12.4, 3.13.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 55.2 
6 
Oct 07 

Divide and Conquer (continued) K&T Ch 5.35.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.18.4 See also CLRS Ch 34 Midterm 
Lab 8 Homework 6 
Oct 30 

Nov 01 

9 
Nov 04 

Approximation Algorithms K&T 11.111.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.113.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 


