CS 174. Combinatorics and Discrete Probability
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
Related Areas:
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
Links: