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 477 (Lubrano), T.,Th. 2.30pm — 3.50 pm
Grad TA: Matteo Riondato (matteo <AT> cs . brown . edu). Office Hours: W. 2pm — 4pm in CIT 321
Head TA: Patrick Clay (pclay <AT> cs . brown . edu). Office Hours: M. 7pm — 9pm in Moonlab (CIT 227)
Email both TA's: cs155tas <AT> cs . brown . edu
Class Email: Don't forget to subscribe to the course mailing list cs155.2011-12.s@lists.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.
The textbook for the course is Probability and Computing: Randomized Algorithms and Probabilistic Analysis by Michael Mitzenmacher and Eli Upfal.
Errata for the 1st Printing, Errata for the 2nd Printing
Last Updated: Jan 24th 2012