| |
|
| Date |
Topic |
Reading |
Assignment |
| W 8/29 |
Stable marriage |
1.1 |
1 out |
| F 8/31 |
Discussion of Assignment 1 |
Assignment 1 |
|
| M 9/3 |
LABOR DAY |
|
|
| W 9/5 |
Undirected graph traversal |
3.1, 3.2 |
|
| F 9/7 |
Implementation and applications of undirected graph traversal |
3.3, 3.4 |
1.1 in |
| M 9/10 |
Directed graph traversal |
3.5, 3.6 |
|
| W 9/12 |
Scheduling to minimize lateness |
4.2 |
1.2 in, 2 out |
| F 9/14 |
Discussion of Assignment 2 |
Assignment 2 |
|
| M 9/17 |
Dijkstra's shortest paths algorithm |
4.4 |
|
| W 9/19 |
Kruskal's minimum spanning tree algorithm |
4.5 |
|
| F 9/21 |
Efficient implementation of Kruskal's algorithm |
4.6 |
2.1 in |
| M 9/24 |
Recurrence relations |
5.1, 5.2 |
|
| W 9/26 |
Closest pair |
5.4 |
|
| F 9/28 |
Review |
|
2.2 in |
| M 10/1 |
TEST 1 |
Covers all course material up to 9/28 |
|
| W 10/3 |
Weighted interval scheduling |
6.1 |
3 out |
| F 10/5 |
Discussion of Assignment 3 |
Assignment 3 |
|
| M 10/8 |
Knapsack |
6.4 |
|
| W 10/10 |
Bellman-Ford shortest paths algorithm |
6.6 |
3.1 in |
| F 10/12 |
Sequence alignment |
6.8 |
|
| M 10/15 |
Ford-Fulkerson maximum-flow algorithm |
7.1 |
|
| W 10/17 |
Max-flow min-cut theorem |
7.2 |
3.2 in, 4 out |
| F 10/19 |
Discussion of Assignment 4 |
Assignment 4 |
|
| M 10/22 |
Bipartite matching |
7.5 |
|
| W 10/24 |
Polynomial-time reductions; satisfiability |
8.1, 8.2 |
4.1 in |
| F 10/26 |
NP |
8.3 |
|
| M 10/29 |
NP-completeness |
8.4 |
|
| W 10/31 |
Review |
|
4.2 in |
| F 11/2 |
TEST 2 |
Covers all course material from 10/3 to 10/31 |
5 out |
| M 11/5 |
Discussion of Assignment 5 |
Assignment 5 |
|
| W 11/7 |
Graph coloring |
8.7 |
|
| F 11/9 |
PSPACE and PSPACE-completeness |
9.1, 9.2 |
|
| M 11/12 |
Undecidability |
|
5.1 in |
| W 11/14 |
Halting Problem |
|
|
| F 11/16 |
Analysis of a greedy load balancing algorithm |
11.1 |
|
| M 11/19 |
Set cover |
11.3 |
5.2 in, 6 out |
| W 11/21 |
Discussion of Assignment 6 |
Assignment 6 |
|
| F 11/23 |
THANKSGIVING |
|
|
| M 11/26 |
Approximation algorithms for vertex cover |
11.4, 11.6 |
|
| W 11/28 |
Random variables; linearity of expectation |
13.3 |
6.1 in |
| F 11/30 |
Randomized selection and sorting |
13.5 |
|
| M 12/3 |
Hashing |
13.6 |
|
| W 12/5 |
Review |
|
6.2 in |
| F 12/7 |
TEST 3 |
Covers all course material from 11/5 onward |
|