Course Outline, Randomized Algorithms

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

cole@cs.nyu.edu (Richard Cole)
Last modified: Jan 13, 1997