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