CMPT 210 - Probability and Computing (Fall 2024)

Lectures (beginning September 5):
D100: Tuesday (8.30 am - 10.20 am) and Thursday (8.30 am - 9.20 am) (AQ 3005)
D200: Tuesday (11.30 am - 1.20 pm) (AQ 3150) and Thursday (11.30 am - 12.20 pm) (C 9002)

Tutorials (beginning September 17):
D100: Friday (11.30 am - 12.20 am, 12:30 pm - 1.20 pm) (WMC 2533 & WMC 3511)
D200: Tuesday (4.30 pm - 5.20 pm) (WMC 2531 & AQ 5035), 5:30 pm - 6.20 pm (WMC 2501 & AQ 5025)

Instructor: Sharan Vaswani
Instructor office hours: Tuesday, 3 pm - 4 pm (TASC-1 8221)

Teaching Assistant: Kaixuan Hu, Dingdong Yang, Haidan Liu, Harsimran Singh
TA office hours: Monday, 12.30 pm - 1.30 pm (ASB 9810), Wednesday, 1 pm - 2 pm (ASB 9804), Wednesday, 4 pm - 5 pm (ASB 9816), Thursday, 1 pm - 2 pm (ASB 9810)

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. R, Fifth Edition. [R]
• Mathematics for Computer Science (Lehman, Leighton, Meyer) [LLM]
• CMU Lecture Notes for Probability and Computing (O'Donnell) [D]
• Randomized Algorithms, Nick Harvey [H]
• Probabilistic Machine Learning: An Introduction, Kevin Murphy [M]

Piazza for course-related questions and discussion.

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 QuickSelect, Voter Poll

Schedule

• CMU
• U Washington
• Stanford