### **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