All references are to the course text.
Week 1. Introduction. Sections 1.1-1.3, 1.5.
Week 2. Fingerprinting. Sections 7.1-7.2,7.4-7.6.
Week 3. Breaking symmetry. Sections 12.5-12.6.
Weeks 4-7. Moments, deviations & Chernoff bounds. Sections 3.1-3.5, 4.1-4.3, 12.2.
Weeks 8-9. Data structures, graph algorithms. Sections 8.2-8.4, 9.7, 10.3.
Week 10. Delay sequence argument for randomized routing in networks (See F.T. Leighton, Introduction to Parallel Algorithms and Architectures, pp. 440-442, 547-554, 571-585).
Weeks 11-14. Other topics according to class interest. Possibilities are Computational Geometry, Cryptography, Markov Chains, Online algorithms. (In reality, I suspect it will take more than 10 weeks to cover the topics listed above.)
There will be more or less weekly homeworks; typically, I will have the due date be two weeks after the date the homework is distributed.
Course Home Page
firstname.lastname@example.org (Richard Cole)
Last modified: Jan 13, 1997