Lecture 1. | Wed, Sep. 8: | Course introduction. Fibonacci heaps (scribe notes). |
Lecture 2. | Fri, Sep. 10: | Persistent data structures (scribe notes). Suffix trees (scribe notes). |
Lecture 3. | Mon, Sep. 13: | Suffix trees (continued) (scribe notes). |
Lecture 4. | Wed, Sep. 15: | Treaps. (scribe notes). |
Recitation 1. | Fri, Sep. 17: | Splay trees (scribe notes). |
Lecture 5. | Mon, Sep. 20: | Hashing: 2-universal, perfect hashing (some notes). Fingerprinting. |
Lecture 6. | Wed, Sep. 22: | Fingerprinting (continued) (some notes, Rabin-Karp). Max flows (scribe notes). |
Lecture 7. | Fri, Sep. 24: | Max flows (continued) (see notes for the previous lecture and these scribe notes). |
Lecture 8. | Mon, Sep. 27: | Max flows (continued) (scribe notes). |
Lecture 9. | Wed, Sep. 29: | Max flows (continued -- max flow of min cost) (scribe notes are the same as for the previous lecture). |
Recitation 2. | Fri, Oct. 1: | Dynamic Trees. Preflow-push algorithm. |
Lecture 10. | Mon, Oct. 4: | Min cost flow algorithms (scribe notes). Linear programming (scribe notes) |
Lecture 11. | Wed, Oct. 6: | Linear programming. Farkas Lemma. Duality. (scribe notes) |
Recitation 3. | Fri, Oct. 8: | Goldberg-Tarjan Min-cost Flow. (scribe notes) |
Lecture 12. | Wed, Oct. 13: | Linear programming: more duality (weak and strong duality). Complementary slackness conditions (scribe notes) |
Lecture 13. | Fri, Oct. 15: | Linear programming: complementary slackness conditions (same scribes as above). |
Lecture 14. | Mon, Oct 18: | LP: Interior points algorithm. Approximation algorithms: constant, relative approximation (scribe notes). |
Lecture 15. | Wed, Oct. 20: | Approximation algorithm (continuation): PAS, FPAS, rounding, enumeration (scribe notes). |
Lecture 16. | Fri, Oct. 22: | Approximation algorithm (continuation): rounding, relaxation (scribe notes). |
Lecture 17. | Mon, Oct. 25: | Approximation algorithm (continuation): LP relaxation, randomized rounding (see previous scribes and these ones). |
Lecture 18. | Wed, Oct. 27: | Fixed parameter tractability. (see the last part of scribe notes). |
Lecture 19. | Fri, Oct. 29: | Fixed parameter tractability -- treewidth. Online algorithms (scribe notes). |
Lecture 20. | Mon, Nov. 1: | Online algorithms (continued): paging, randomization , potential functions (see previous scribes and these ones). |
Lecture 21. | Wed, Nov. 3: | Randomized online algorithms(adversarial models, Marking algorithm) |
Lecture 22. | Fri, Nov. 5: | Lower bounds for randomized online algorithms. Geometry: range search (last part of scribe notes). |
Lecture 23. | Mon, Nov. 8: | Convex Hulls, voronoi diagrams. |
Lecture 24. | Wed, Nov. 10: | Voronoi Diagrams(cont'd), randomized incremental construction: binary space partition. |
Lecture 25. | Fri, Nov. 12: | Backwards Analysis for RIC: convex hull, linear programming. |
Lecture 26. | Mon, Nov. 15: | External memory algorithms (scribe notes). |
Lecture 27. | Mon, Nov. 17: | Cache-oblivious algorithms (scribe notes). |