Boston University - Fall 2023
CAS CS 237 - Probability in Computing

Instructors and Course Staff

Name Office Hours Room
Prof. John Byers Mon, 10:00am-11:30am
Thu, 10:00am-11:30am
Prof. Tiago Januario Mon, 04:00pm-05:00pm
Wed, 04:00pm-06:00pm
Teaching Fellow: Ephraim Linder Check Google Calendar
Teaching Assistants: Eric Wang, Jiawei Sun, Noah Barnes
Course Assistants: Annie Huang, Can Wang, Jessica Nguyen, Lin Khant Ko, Michael Krah, Munir Siddiqui, Oscar Mo, Quang Nguyen, Shengduo Li, Steve Choi


  • We will use Piazza for online discussions.
  • Do not send e-mails to the course staff.
  • Feel free to ask or answer questions on Piazza.
  • Bonus points will be granted to good questions and good answers.
  • You are not allowed to post solutions online.
  • For sensitive, specific questions and solutions, use private posts.


We assume good working knowledge of elementary set theory and counting, elementary calculus (i.e., integration and differentiation), and programming in Python.


  • Two 75 minutes lectures taught by one Instructor
    • Section A: CGS505, Tuedays and Thursdays, from 2:00pm to 3:15pm
    • Section B: CGS129, Tuedays and Thursdays, from 3:30pm to 4:45pm
  • One 50 minutes discussion lab on Fridays (check your schedule on Student Link)
  • Attendance in lectures and discussion is mandatory
The two sections of the course, A and B, will be treated as one class. The content of the two lectures is identical, assignments will be shared, students can mix-and-match A and B lecture.


Introduction to basic probabilistic concepts and methods used in computer science. Develops an understanding of the crucial role played by randomness in computing, both as a powerful tool and as a challenge to confront and analyze. Emphasis on rigorous reasoning, analysis, and algorithmic thinking. This course fulfills a single unit in each of the following BU Hub areas: Quantitative Reasoning II, Critical Thinking.


This schedule is subject, and likely, to change as we progress through the semester. Reading chapters are from the first textbook (LLM) or from the second textbook (P), referred to by the acronyms of the author names.

Lec. Date (Tentative) Topics Reading Handouts/Homework Instructor
1 Tue, Sep 05 Course information, Tips to succeed
Random experiments

P 1.1
P 1.2
Google Colab
Collaboration & Honesty Policy
2 Thu, Sep 07 Sample spaces, events
Probability function

Slides with notes
LLM 17.1
P 1.3.1-1.3.3
HW1 out TJ
3 Tue, Sep 12 Probability axioms and rules
Computing probabilities

Slides with notes
LLM 17.3
LLM 17.5
P 2
Non-transitive Dice
4 Thu, Sep 14 Tree diagrams
The Monty Hall problem

LLM 17.2
LLM 18.1.2
HW2 out JB
5 Tue, Sep 19 Continuous Probability Spaces
Anomalies with Continuous Probability

P 1.3.5 Video JB
6 Thu, Sep 21 Random variables
Definition and examples
Application of recommender systems

LLM 19.1
P 3.1.1
P 4.1.0
HW3 out JB
7 Tue, Sep 26 Distribution Functions
  • Probability Mass Function
  • Probality Density Function
  • Cummulative Distribution Function
P 3.1.2
P 3.1.3
P 3.2.1
P 4.1.0
P 4.1.1
Video JB
8 Thu, Sep 28 Properties of PMFs, PDFs and CDFs
Examples and applications.
P 3.1.6
P 4.1.4
HW4 out TJ
9 Tue, Oct 03 Conditional probability
Product rule
LLM 18
P 1.4.0
Game: higher or lower?
10 Thu, Oct 05 Law of total probability
Bayes' Rule

P 1.4.2
P 1.4.3
HW5 out TJ
Tue, Oct 10 Monday Schedule
Last Day to Drop without a “W” grade
11 Thu, Oct 12 Independent events
Pairwise Independence
Mutual independence
LLM 18.7
LLM 18.8
HW6 out JB
12 Tue, Oct 17 People versus Collins
Independence of random variables
LLM 18.9
P 1.4.1
13 Thu, Oct 19 Expected value of a random variable
Infinite sums
LLM 19.4
P 3.2.2
Practice Problems out TJ
14 Tue, Oct 24 Linearity of Expectation LLM 19.5
P 6.1.2
Practice Problems Solution out TJ
Thu, Oct 26 Midterm HW7 out
15 Tue, Oct 31 Expectation of continuous random variables
Conditional expectation
LLM 19.4.1
P 3.2.3
16 Thu, Nov 02 Law of total expectation
Linearity of conditional expectation
LLM 19.4.6
HW8 out JB
17 Tue, Nov 07 Variance
Standard deviation
Variance properties
LLM 20.3
P 3.2.4
Video JB
18 Thu, Nov 09 Discrete distributions:
- Bernoulli, Uniform,
- Binomial, Geometric,
- Negative Binomial
LLM 19.3.1
LLM 19.3.2
P 3.1.5
HW9 out TJ
Mon, Nov 13 "Last Day to Drop Standard Courses (with a “W” grade)
Last Day for Undergraduate Students to Designate a Course as Pass/Fail"
19 Tue, Nov 14 Coupon Collector
Reservoir Sampling
LLM 19.5.4
20 Thu, Nov 16 Markov inequality
Chebyshev inequality
LLM 20.1
LLM 20.2
P 6.2.2
HW10 out TJ
21 Tue, Nov 21 Applications of Markov and
Chebyshev's inequalities
LLM 20.1.1
LLM 20.2.1
Thu, Nov 23 Thanksgiving HW 11 out
22 Tue, Nov 28 Continuous distributions I:
- Uniform
- Normal
LLM 20.2.2
P 4.2.3
23 Thu, Nov 30 Continuous distributions II:
- Exponential
- Poisson Process
P 4.2.2
P 11.1.2
HW 12 out JB
24 Tue, Dec 05 Probability in Algorithms:
- Bucket Sort
CLRS 8.4 Final Practice Problems out JB
25 Thu, Dec 07 Probability in Data Structures:
- Bloom Filters
CLRS 11.3
26 Tue, Dec 12 Review Final Practice Solutions out TJ
27 Thu, Dec 14 Study Period
28 Fri, Dec 15 Final exam period begins
29 Thu, Dec 21 Final exam period ends


You can access both books for free or support the authors by purchasing the books.

Course atmosphere, diversity and inclusion

  • We intend to provide a positive and inclusive atmosphere in classes and on the associated virtual platforms.
  • If you require special accommodations for exams or coursework, please send a private message to an instructor and forward any relevant documentation from Disability and Access Services.
  • If you are facing unusual circumstances during the semester, please reach out to us early on so that we can find a good arrangement.
Your suggestions are encouraged and appreciated. Please let us know ways to improve the effectiveness of the course for you personally or for other students.

Attendance and participation

  • Attendance will be tracked with Top Hat
  • Students must attend at least 75% of both lectures and discussion labs to pass the course.
  • Your participation grade depends on answering TopHat questions, which requires your presence in class.
  • You will get the full 5% of the course grade if you get at least 75% of the possible TopHat points.
  • Most of the material covered in lectures and labs can be found in our textbooks. Read them!
  • While our textbook will be very helpful, it is an imperfect substitute for in-class learning, which is the fastest (and easiest) way to learn the material.
  • In all cases, you are responsible for being up to date on the material.
Course TopHat page:
Join Code: 445364


  • There will be weekly homework assignments posted on Thursdays.
  • Assignments will be due Wednesdays by 09:00PM ET, electronically via Gradescope.
  • You are responsible for submitting high-quality images of your solutions. Illegible submissions will receive a 0 grade
  • We highly recommend Gradescope Mobile App. You can also use your favorite app from iPhone or Android.
  • Late assignments will not be accepted as we intend to post solutions the following day.
  • The lowest grade on your homework assignments will be dropped.
  • Submissions with identical worded answers, including identical pseudocode, will receive no grade.
  • Any use of ChatGPT or similar AI functionality to help solve homework problems is a violation of the Collaboration & Honesty Policy.
Sometimes it's ok to submit partial results if you couldn't fully finish your assignment, don't miss the due date because of last-minute work.


  • Both exams will consist of problem-solving and short questions about the material.
  • Each exam duration and their locations are given in the course schedule.
  • The content of the final is cumulative.
  • No collaboration whatsoever is permitted on exams, any violation will be reported to the College.

Regrade Policy

  • Regrade requests can be submitted up to one week (7 days) after grades for a given assignment have been posted (except the final exam).
  • You must request a regrade via Gradescope, *NOT* through email .
  • When we regrade a problem, your score may go up or down.


The course grade will break down as follows:
  • 5% class attendance and participation with Top Hat
  • 30% weekly homework assignments
  • 30% in-class midterm exam
  • 35% in-class final exam. Don't make any travel plans before the final date is released
  • Incompletes for this class will be granted based on CAS Policy.
Participating in lectures, discussions, and on Piazza, bonus participation points will be awarded to students who get the most “good questions” and “good answers” on Piazza. Only good questions on the course material (not logistics) will be counted.

Citation policy

  • You can refer to anything from the textbook, lecture and discussion notes, and information given by the course staff without having to cite it.
  • If you use any other information, you must include a proper citation. If you omit to do this, you are committing plagiarism.
  • Searching explicitly for answers to problems on the Web or from persons not enrolled in the class this current semester is strictly forbidden.

Collaboration & Honesty Policy

  • The Collaboration & Honesty Policy specifies the rules of collaboration in the course and penalties for cheating.
  • We require that each student read, sign, and submit this document to Gradescope.
  • Even if you get help on Piazza or during office hours from the instructors for the class for specific problems, list them as collaborators.


Sample nameplate
Change the name to yours in this PPTX file, print it, and bring it to the labs.

LaTeX resources
TexShop is a latex editor for the Mac platform; TexNiCenter is a text editor for Windows; Overleaf is a web-based latex system (that allows you to avoid latex installation on your machine). Not so short intro to latex; a latex tutorial.

Homework template files: tex, pdf, jpg.

This document was last modified: