CMPT 210 - Probability and Computing (Spring 2023)

Instructor: Sharan Vaswani
Instructor office hours: Thursday 2.30 pm - 3.30 pm (TASC-1 8221)

Teaching Assistant: Anh Dang
Tutorials: Monday (1:30 pm - 2:20 pm) (BLU 10921), Monday (3.30 pm - 4.20 pm) (BLU 10921)

Course Objective: The course introduces the foundational concepts in probability as required by many modern applications in computing. It will give the students in Computing Science experience in: 1. Understanding the combinatorial nature of many computational problems. 2. Working knowledge of probability theory, with applications to computing (algorithms, machine learning, data analysis, etc.)

Prerequisites: MACM 101, MATH 152 and MATH 232/MATH 240

Textbook: There is no required textbook. We will use the following resources:

• Introduction to Probability and Statistics for Engineers and Scientists, Sheldon M. Ross, Fifth Edition.
• Mathematics for Computer Science (Meyer, Lehman, Leighton)
• CMU Lecture Notes for Probability and Computing (O'Donnell)
• Randomized Algorithms (Harvey)
• Probabilistic Machine Learning: An Introduction (Murphy)

Piazza for course-related questions.

List of topics

• Combinatorics: Permutations, Binomial coefficients, Inclusion-Exclusion
• Basic probability theory: Independence, Conditional probability, Bayes' Theorem
• Basic probability theory: Random variables, Expectation, Linearity of Expectation, Variance
• Discrete distributions: Binomial and Geometric, Joint distributions
• Tail inequalities: Markov’s Inequality, Chebyshev’s Inequality, Chernoff Bound
• Applications: Verifying matrix multiplication, Max-Cut, Machine Learning, Randomized QuickSort, AB Testing
• Continuous distributions (Introduction): Normal Distribution, Central Limit Theorem

Schedule

• CMU
• U Washington
• Stanford