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

Also Offered As: COMPSCI 174

Related Areas:

• Security (SEC)
• Theory (THY)

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: Student Option

Final Exam Status: Yes

---

Links:

• EECS Course Archives (CalNet authentication required)
• CS enrollment policies
• EE enrollment policies
• HKN course maps