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 | Max-flow: Ford-Fulkerson algorithm | Section 7.1 | |
14 | Max-flow residual graphs | Section 7.2 | |
15 | Max-flow Min Cut Theorem (using Ford-Fulkerson) | 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 3-SAT | Section13.4, 13.5 | |
19 | Polytime Reductions. The class NP | Section 8.1 | |
20 | NP hardness, NP-completeness. Vertex Cover, Independent Set | Chapter 8 | |
21 | More NP-completeness Proofs: 3-SAT, Hamiltonian Cycle, Hamiltonian Path, TSP | Chapter 8 |