Computer Science 174 — Combinatorics and Discrete Probability (4 Units)

Course Overview

Summary

Prerequisites

A class with a sizable probability component would probably help (Math55 or CS70), but a probability-heavy course (Stat134 or EE126) would help more.

Topics Covered

• Events and probability
• Random Variables, Expectation, conditional expectation
• Bernoulli, binomial, geometric distributions
• Program Checking/Polynomial Identities
• Coupon collector’s problem
• Variance and moments
• Markov’s inequality, Chebyshev’s inequality
• Chernoff bounds, moment generating functions
• Hoeffding-Azuma inequality
• Balls and bins, the birthday paradox
• Routing in a Parallel Computer
• The Poisson distribution, the Poisson approximation
• Hashing, Bloom filters
• Random Graphs
• The probabilistic method, Lovasz local lemma
• Markov chains
• Stationary distributions, classification of states
• Random walks
• The Monte Carlo method, Markov chain Monte Carlo
• Coupling of Markov chains
• Graph Algorithms: Minimum cut, independent sets, Hamiltonian cycles
• Randomized algorithms for satisfiability

Workload

Course Work

Time Commitment

Choosing the Course

When to take

What's next?

Usefulness for Research or Internships

Additional Comments/Tips

Last edited: Summer 2020