DRAFT
CS/IDS 150 ab

Probability and Algorithms

9 units (3-0-6)    |  first, third terms
Prerequisites: part a: CS 38 and Ma 5 abc; part b: part a or another introductory course in discrete probability.

Part a: The probabilistic method and randomized algorithms. Deviation bounds, k-wise independence, graph problems, identity testing, derandomization and parallelization, metric space embeddings, local lemma. Part b: Further topics such as weighted sampling, epsilon-biased sample spaces, advanced deviation inequalities, rapidly mixing Markov chains, analysis of boolean functions, expander graphs, and other gems in the design and analysis of probabilistic algorithms. Parts a & b are given in alternate years.

Instructor: Schulman

Please Note

The online version of the Caltech Catalog is provided as a convenience; however, the printed version is the only authoritative source of information about course offerings, option requirements, graduation requirements, and other important topics.