Probability, randomness and statistics play a key role in modern computer science. From the highly theoretical notion of probabilistic theorem proving, to the very practical applications of cryptography and web search ranking, sophisticated probabilistic techniques have been developed in the last two decades for a broad range of challenging computing applications.
This course introduces the basic probabilistic techniques used in the design of randomized algorithms and in probabilistic analysis of algorithms. The course covers the basic probability theory required for working with these techniques, and demonstrates their use in various computing applications.
Among the topics covered in the course:
The concept of randomized algorithm - fingerprinting - verifying polynomial identities,
Randomized algorithms vs. probabilistic analysis of algorithms.
Moments and deviations - randomized selection algorithm.
Chernoff and Hoeffding's tail bounds - parallel packet routing.
Balls bins and random graphs - the coupon collector paradigm: hashing, Bloom filter, Hamiltonian cycles in random graphs.
The probabilistic method - from existential proofs to explicit constructions.
Markov chains - randomized 2-sat and connectivity algorithms.
Continuous distribution and the Poisson process - basic queuing processes.
Algorithmic applications of information theory.
Instructor: Eli Upfal (eli <AT> cs . brown . edu), CIT 473, x37601
Lecture Place and Hours: CIT 368, T.,Th. 1:00 - 2:20 pm
TA: Victor Naroditskiy (vnarodit <AT> cs . brown . edu)
Newsgroup: cs155 -- do not forget to subscribe.
60% homework (including midterm). Midterm is a non-collaborative homework set.
40% take home final. Deadline about 10 days after end of class.
The textbook of the course is
by Michael Mitzenmacher and Eli Upfal.