|
Week |
Monday |
Wednesday |
Friday |
|||
|
0 |
|
|
9/24 |
Introduction & Stable Matching |
9/26 |
Stable Matching & Overview
|
|
1 |
9/29 |
Graph Traversal |
10/1 |
Graph Traversal Connectivity, Topological
Sort |
10/3 |
Greedy Algorithms Interval Scheduling Homework1 due |
|
2 |
10/6 |
Greedy Algorithms Interval Partitioning,
Minimizing Lateness |
10/8 |
Greedy Algorithms Offline Caching (Belady’s Alg) |
10/10 |
Greedy Algorithms Shortest Paths, Minimum Spanning
Trees Homework2 due |
|
3 |
10/13 |
Divide & Conquer Bisection, Repeated Squaring,
Closest Pair, Master Recurrence |
10/15 |
Divide & Conquer Strassen’s Algorithm, Karatsuba’s
Algorithm |
10/17 |
Divide & Conquer
Fast Fourier
Transform Homework3 due |
|
4 |
10/20 |
Divide & Conquer Linear Time Selection, Quicksort analysis |
10/22 |
Dynamic Programming Fibonacci, Weighted Interval
Scheduling |
10/24 |
Dynamic Programming
Segmented Least Squares, Knapsack/Subset Sum Homework4 due |
|
5 |
10/27 |
Dynamic Programming RNA Secondary Structure, Edit Distance |
10/29 |
Dynamic Programming Edit Distance, Bellman-Ford |
10/31 |
Bellman-Ford on Dags Bipartite Matching & Network Flow Intro Homework4 Bonus
due |
|
6 |
11/3 |
MIDTERM Content to 10/24 |
11/5 |
Network Flow Ford-Fulkerson |
11/7 |
Network Flow Capacity Scaling Homework5 due |
|
7 |
11/10 |
Network Flow Edmonds-Karp |
11/12 |
Network Flow
Applications |
11/14 |
Network Flow More Applications Homework6 due |
|
8 |
11/17 |
Polynomial-time Reductions |
11/19 |
P/NP More
reductions Certificates, P, NP |
11/21 |
NP-completeness 3- Homework7 due |
|
9 |
11/24 |
NP-completeness Hamiltonian
Circuit, |
11/26 |
|
11/28 |
NO CLASS Thanksgiving |
|
10 |
12/1 |
|
12/3 |
Homework8 due |
12/5 |
|
|
11 |
12/8 |
FINAL EXAM (cumulative) 12/8 2:30pm Johnson 111 |
|
|
|
|