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