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 offered in alternate years.
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.