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 319, x37645
Lecture Place and Hours: CIT 368, T.,Th. 1:00 - 2:20 pm
Grad TA: Aparna Das (aparna
<AT> cs . brown . edu).
Head TA: Borislav Hristov (bhristov <AT> cs . brown . edu).
Email Both TAS: (cs155tas<AT> cs . brown . edu).
Class Email: Don't forget to subscribe cs155@list.cs.brown.edu
60% homework (including midterm). Midterm is a non-collaborative homework set.
40% take home final. Deadline about 10 days after end of class.
Borislav: Sunday, 8-10pm in CIT 271 (temporarily)
Aparna: Tuesday, 6:00-8:00pm in CIT 271
The textbook of the course is
by Michael Mitzenmacher and Eli Upfal.