Catalog Description: Permutations, combinations, principle of inclusion and exclusion, generating functions, Ramsey theory. Expectation and variance, Chebychev's inequality, Chernov bounds. Birthday paradox, coupon collector's problem, Markov chains and entropy computations, universal hashing, random number generation, random graphs and probabilistic existence bounds.

Units: 4

Prerequisites: COMPSCI 170

Formats:
Fall: 3.0 hours of lecture and 1.0 hours of discussion per week
Spring: 3.0 hours of lecture and 1.0 hours of discussion per week

Grading basis: letter

Final exam status: Written final exam conducted during the scheduled final exam period


Class homepage on inst.eecs


Department Notes:

Course objectives: Provide familiarity with basic tools in discrete probability and their applications to the design and analysis of randomized algorithms and data structures. Learn how probabilistic ideas and techniques can lead to more efficient and conceptually simpler algorithms for many problems. Develop an understanding of randomness as a computational resource.

Topics covered:

Related Areas: