Probability and Computing. (3-0) 3 Credit Hours

Catalog description

Prerequisites: CS 3333 or MAT 2313 . May include moments of random variables: randomized mincut algorithm, Chebyshev and Markov inequalities, sampling estimator for mean. Basic Concentration Inequalities: Chernoff and Hoeffding inequalities; parameter estimation and set balancing. Discrete probabilistic structures: Bucket sort algorithm, Poisson approximation, Lovasz local Lemma, independent set search. The Gaussian: Moment Generating Functions, Central Limit Theorem, JL dimensionality reduction lemma. Markov Chains and Random Walks: Stationary Distributions, and randomized 3-SAT algorithm, Entropy Function: Information and Compression. (Cross-listed with MAT 4333 . Credit cannot be earned for both MAT 4333 and CS 4333 .) Generally offered in Springs. This course has Differential Tuition. Course fees: IUCA $45; DL01 $75.