Probability and Computing

Catalog description

(same as CMP_SC 4525 ; cross-leveled with MATH 7525 , CMP_SC 7525 ) This course is concerned with probabilistic methods in computer science and discrete mathematics. Its goal is to study the interplay between probability and computational complexity, and to demonstrate how tools from modern probability theory can be exploited in the study of structures that depend on many parameters, such as networks with many nodes and functions of many variables. Covered topics may include: discrete probability, concentration inequalities, martingale methods, the probabilistic method, entropy and information, Vapnik-Chervonenkis theory. Applications to (theoretical) computer science, combinatorics, random graphs, randomized algorithms, probabilistic analysis, derandomization. Graded on A-F basis only. Credit Hour s : 3 Prerequisites: MATH 2320 or MATH 3000W ; STAT 4710 / STAT 7710 or STAT 4750 / STAT 7750 Recommended: MATH 4120 / MATH 7120 ; MATH 4140 / MATH 7140