| WEEK |
DAY |
ANNOUNCEMENTS |
TOPIC & READING |
LAB |
| 1 | Jan 19 | | Course Introduction
Stable Matching
K&T Ch1 | Lab 1
Homework 1 |
Jan 21 | |
Jan 23 | |
| 2 | Jan 26 | | Analysis
K&T Ch 2.1-2.4 | Lab 2
Homework 2 |
Jan 28 | |
Jan 30 | Drop/Add ends |
| 3 | Feb 02 | | Analysis continued
K&T Ch 2.1-2.4 | Homework 3 |
Feb 04 | | classes cancelled |
Feb 06 | |
| 4 | Feb 09 | | Graph Algorithms
K&T Ch 3 | Lab 4
Homework 4
partners |
Feb 11 | |
Feb 13 | |
| 5 | Feb 16 | | Greedy Algorithms
K&T Ch 4 | Lab 5
Homework 5 |
Feb 18 | |
Feb 20 | |
| 6 | Feb 23 | | Divide and Conquer
K&T Ch 5 | Lab 6
Homework 6 |
Feb 25 | |
Feb 27 | |
| 7 | Mar 02 | Midterm (Mar 03) | Divide and Conquer (continued)
K&T Ch 5 |
|
Mar 04 | |
Mar 06 | | no class
(SIGCSE conference) |
| | Mar 09 | Spring Break |
Mar 11 |
Mar 13 |
| 8 | Mar 16 | | Dynamic Programming
K&T Ch 6 | Lab 8
Homework 7 |
Mar 18 | |
Mar 20 | |
| 9 | Mar 23 | | Intractability
K&T 8.1-8.4
See also CLRS Ch 34 | Lab 9
Homework 8 |
Mar 25 | |
Mar 27 | Last day to declare CR/NC or withdraw
with a "W" |
| 10 | Mar 30 | | Approximation Algorithms
K&T 11.1-11.4, 11.6, 11.8
See also CLRS Ch 35 | Lab 10
Homework 9 |
Apr 01 | |
Apr 03 | |
| 11 | Apr 06 | | Randomized Algorithms
K&T 13.1-13.5 | Lab 11 |
Apr 08 | |
Apr 10 | |
| 12 | Apr 13 | | Lower Bounds | Lab 12
Homework 10 |
Apr 15 | |
Apr 17 | |
| 13 | Apr 20 | | Alternate Models of Computation:
Streaming Algorithms
The Space Complexity of Approximating The Frequency Moments, by Alon, Matias, Szegedy STOC 1996. | Lab 13 |
Apr 22 | |
Apr 24 | |
| 14 | Apr 27 | | Final projects, class review |
|
Apr 29 | |
May 01 | |