All readings are from the text unless otherwise indicated.
Topic | Date | Reading | Lecture |
---|---|---|---|
7/1 | §1.2 | introduction | |
Greedy algorithms | 7/2 | §1.1 | stable matching |
7/3 | §4.1, §4.2 | interval scheduling, minimizing lateness | |
7/4 | notes | no class (happy independence day!) | |
7/5 | §4.5 | minimum spanning trees | |
7/8 | — | Kruskal's algorithm | |
Divide and conquer | 7/9 | §5.1, §5.2 | mergesort, solving recurrences, master theorem |
7/10 | §5.5, §6.1, §6.2 | large integer multiplication | |
Dynamic programming | fibonacci, memoization, weighted interval scheduling | ||
7/11 | §6.6 | sequence alignment | |
7/12 | §6.8 | Bellman-Ford | |
Flow | 7/15 | browse chapter 7 | network flow, a cornucopia of problems |
7/16 | review | ||
7/17 | prelim I | ||
7/18 | §7.1 | Ford-Fulkerson | |
7/19 | §7.2 | max-flow min-cut theorem | |
7/22 | §7.3 | delta-scaling, circulation | |
7/23 | §7.7 | circulation with lower bounds | |
NP completeness | §8.1 | polynomial time reductions | |
7/24 | §8.3, § 8.4 | definitions of P, NP, NP-hard, NP-complete, | |
§8.2 | vertex cover and independent set | ||
7/25 | §8.2 | fun with SAT | |
7/26 | §8.5 | Hamiltonian paths | |
7/29 | §8.1, §8.5 | traveling salesman problem, set cover | |
7/30 | §8.6, §8.7, §8.8 | 3-coloring, 3d matching, subset sum | |
§8.10 | taxonomy of NP-complete problems | ||
Undecidability | 7/31 | notes, §1, §2 | Turing machines |
8/1 | notes, §5.2 | proving Cook-Levin, nondeterministic Turing machines | |
8/2 | notes, §3 | universal turing machines | |
8/5 | notes, §4.1–§4.4 | undecidability, the halting problem | |
8/6 | notes, §4.5 | Rice's theorem |
The course grade will be based on the homeworks (roughly 20%), the exams (roughly 20% prelim I, 20% prelim II, 25% final exam), and class participation (roughly 15%, including mini problem sets that I will give for discussion).
Academic integrity is important for two reasons. The first is that the course is designed to help you learn the material. If you don't do the work you won't learn the material. The second is that we grade you; this would be meaningless if the work we grade is not yours.
You are encouraged to work together to figure out solutions to the problem sets. However, the work you submit should be your own; copying others' papers is forbidden. My strategy is to write rough notes while working with others and then try to write up my submission without referencing them. This ensures both that I learn the material, and that I comply with the requirements of integrity.