Schedule: Fall 2018

(under construction)

Aug 20. Computability and Undecidability. Notes (draft)

Aug 22. Incompleteness. Notes (draft)

Aug 27. Divide and Conquer I: Multiplication, Median. Notes (draft)

Aug 29, 5. D & C II: Fast Fourier Transform, pattern matching. Notes1, Notes2 (draft).

Sept 10, 12. Time, space, nondeterminism, Savitch’s theorem Notes1, Notes2 (draft).

Sept 17. Greedy algorithms Notes (draft)

Sept 19. Exam 1

Sept 24, 26. Dynamic Programming Notes1 Notes2 (draft)

Oct 1, 3 Linear equations Notes1 Notes 2 (draft)

Oct 10, 15 Maxflow and Mincut Notes

Oct 17, 22. Matchings Notes1, Notes2

Oct 24, 29. Linear Programs Notes2 Notes1

Oct 31. Exam 2

Nov 5, 7. Linear and Convex Optimization Notes (Ellipsoid)

Nov 12, 14 NP-completeness, SAT is NP-complete. Notes Karp’s 21

Nov 19. PSPACE, reductions, Completeness. draftNotes

Nov 26. Exercises (reductions, Linear Programming) Notes

Nov 28. Exam 3

Dec 3. Randomization and Approximation.

 

Advertisements