Office Hours: TBA
Lecture: MWF 9:30 10:20 in Ry 251
Office hours: TBA
Other useful sources:

Grading will be based on weekly homework assignments, two midterms and a final.
Lecture  Topics  Reading  
1  Stable matchings  Chapter 1  
2  Running time analysis  Chapter 2  
3  Interval Scheduling  Section 4.1,4.2  
4  Minimum Spanning Trees  Section 4.5  
5  Heaps, and other data structures; Shortest paths  Section 4.6  
6  Implementing Dijkstra, Divide (into "equal" parts) and Conquer  Section 4.4  
7  Sequence Alignment  Section 6.7  
8  More sequence Alignment: using little space  Section 6.6  
9  More Dynamic Programming: optimal matrix multiplication sequence  
10  Even more Dynamic Programming: Top Down vs Bottom Up  Section 6.2  
11  Max Flow Problem  
13  Maxflow: FordFulkerson algorithm  Section 7.1  
14  Maxflow residual graphs  Section 7.2  
15  Maxflow Min Cut Theorem (using FordFulkerson)  Section 7.3  
15  Network Flows: scaling algorithms  Chapter 7  
16  Applications of Max Flow: matchings, Hall's Theorem,  Section 7.5, 7.7  
17  Extensions: multiple sources and sinks. Circulations.  
18  Applications of Max Flow  Chapter 7  
19  Randomized Algorithms. Contention in Distributed Computation  Chapter 13 (beginning)  
20  Randomized Access to Resource. Karger's Global Min Cut Algorithm  Section 13.2  
21  Randomized median. Quicksort. Randomized Max 3SAT  Section13.4, 13.5  
19  Polytime Reductions. The class NP  Section 8.1  
20  NP hardness, NPcompleteness. Vertex Cover, Independent Set  Chapter 8  
21  More NPcompleteness Proofs: 3SAT, Hamiltonian Cycle, Hamiltonian Path, TSP  Chapter 8 