Probability and Computing
Course ID 15259
Description Probability theory is indispensable in computer science today. In areas such as artificial intelligence and computer science theory, probabilistic reasoning and randomization are central. Within networks and systems, probability is used to model uncertainty and queuing latency. This course gives an introduction to probability as it is used in computer science theory and practice, drawing on applications and current research developments as motivation. The course has 3 parts: Part I is an introduction to probability, including discrete and continuous random variables, heavy tails, simulation, Laplace transforms, z-transforms, and applications of generating functions. Part II is an in-depth coverage of concentration inequalities, like the Chernoff bound and SLLN bounds, as well as their use in randomized algorithms. Part III covers Markov chains (both discrete-time and continuous-time) and stochastic processes and their application to queuing systems performance modeling. This is a fast-paced class which will cover more material than the other probability options and will cover it in greater depth.
Key Topics
Probability on events, Concentration inequalities, Discrete-time Markov Chains (with ergodicity proofs) and Continuous-time Markov chains
Course Goals
Analyze probabilities and expectations using tools such as conditioning, independence, linearity of expectations.
Compute expectation and variance of common discrete and continuous random variables.
Apply z-transforms and Laplace transforms to derive higher moments of random variables.
Prove elementary theorems on probability.
Analyze tail probabilities via Markov, Chebyshev, and Chernoff bound concentration inequalities.
Design randomized algorithms and analyze their efficiency.
Model problems using discrete-time and continuous-time Markov chains.
Derive limiting probabilities of Markov chains.
Construct and analyze models for performance analysis of queueing networks.
Understand the application of probability to problems in machine learning, theoretical computer science, networking, cloud computing, and operations research.
Pre-required Knowledge
15-259 assumes NO PRIOR PROBABILITY/STATS classes, and will satisfy the Computer Science Probability/Statistics requirement. The course DOES assume that you have taken calculus (and still remember how to integrate, differentiate, and do Taylor-series expansions). Prior classes in 3D Calculus and Linear Algebra are highly. recommended, and are listed as prerequisites.
Assessment Structure
Weekly homework -- worth 35% combined.
Midterm 1 -- worth 20%.
Midterm 2 -- worth 20%.
Final -- worth 20%.
Occassional Unannounced Quizzes -- worth 5%.
Class Participation -- I will move you up if you're near a grade border and you participate heavily.
Extra Time Commitments
This course 15-259 is for undergraduates. Graduate students should enroll in 15-659.