Boston University - Spring 2024
CAS CS 237 - Probability in Computing


Instructors and Course Staff

Name Office Hours
Prof. Alina Ene Google Calendar
Prof. Tiago Januario
Teaching Fellows: Cheng-Hao Fu, Spyros Dragazis
Teaching Assistants: Eric Wang, Noah Barnes
Course Assistants: Annie Huang, Can Wang, Isaac Hu, Jessica Nguyen, Michael Krah, Munir Siddiqui, Oscar Mo, Quang Nguyen, Ruichen Liu, Sean Lin, Steve Choi

Communication

  • 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.
  • For sensitive, specific questions and solutions, use private posts.

Prerequisites

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

Structure

  • Two 75 minutes lectures taught by one Instructor
    • Section A: LAW AUD, Tuedays and Thursdays, from 2:00pm to 3:15pm
    • Section B: CAS 522, Tuedays and Thursdays, from 3:30pm to 4:45pm
  • One 50 minutes discussion lab on Fridays (check your schedule on Student Link)
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.

Syllabus

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.

Schedule

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 Thu, Jan 18 Course information, Tips to succeed
Random experiments

P 1.1
P 1.2
OB 1B
hw01 out
Google Colab
Collaboration & Honesty Policy
TJ
2 Tue, Jan 23 Sample spaces, events
Probability function

Slides with notes
LLM 17.1
P 1.3.1-1.3.3
AE
3 Thu, Jan 25 Probability axioms and rules
Computing probabilities

Slides with notes
LLM 17.3
LLM 17.5
P 2
hw02 out
Non-transitive Dice
Video
AE
4 Tue, Jan 30 Tree diagrams
The Monty Hall problem

LLM 17.2
LLM 18.1.2
AE
5 Thu, Feb 01 Continuous Probability Spaces
Anomalies with Continuous Probability

P 1.3.5 hw03 out
Video
AE
6 Tue, Feb 06 Random variables
Definition and examples
Distribution Functions
  • Probality Density Function
  • Cummulative Distribution Function
LLM 19.1
P 3.1.1
P 4.1.0
P 3.1.2
P 3.1.3
P 3.2.1
P 4.1.0
P 4.1.1
AE
7 Thu, Feb 08 Properties of PDFs and CDFs
Examples and applications.
P 3.1.6
P 4.1.4
hw04 out
Video
AE
8 Tue, Feb 13 Snow emergency
Stay warm!
AE
9 Thu, Feb 15 Conditional probability
Product rule
LLM 18
P 1.4.0
hw05 out
Game: higher or lower?
AE
10 Tue, Feb 20 Law of total probability
Bayes' Rule

P 1.4.2
P 1.4.3
3Blue1Brown
Veritasium
AE
11 Thu, Feb 22 Independent events
Pairwise Independence
Mutual independence
LLM 18.7
LLM 18.8
hw6 out
Last Day to Drop Standard Courses (without a “W” grade)
TJ
12 Tue, Feb 27 People versus Collins
Independence of random variables
LLM 18.9
P 1.4.1
Video
TJ
13 Thu, Feb 29 Expected value of a random variable
Infinite sums

Slides with notes A1
Slides with notes B1
LLM 19.4
P 3.2.2
hw07 out TJ
14 Tue, Mar 05 Expectation of continuous random variables
Linearity of Expectation

Slides with notes
LLM 19.5
P 6.1.2
TJ
15 Thu, Mar 07 Law of the unconscious statistician
Conditional expectation
Law of total expectation
Linearity of conditional expectation
LLM 19.4.1
P 3.2.3
LLM 19.4.6
No homework this week
Midterm practice Problems out
TJ
Tue, Mar 12 Spring Recess
Thu, Mar 14
16 Tue, Mar 19 Midterm review Midterm Practice Problems Solution out TJ
Thu, Mar 21 Midterm, in class, during lecture time Covers all topics up to Lecture 15
17 Tue, Mar 26 Variance
Standard deviation
Variance properties

Slides with notes
LLM 20.3
P 3.2.4
Video TJ
18 Thu, Mar 28 Discrete distributions:
- Bernoulli,
- Uniform,
- Binomial
LLM 19.3.1
LLM 19.3.2
P 3.1.5
hw08 out TJ
Fri, Mar 29 "Last Day to Drop Standard Courses (with a “W” grade)
Last Day for Undergraduate Students to Designate a Course as Pass/Fail"
19 Tue, Apr 02 Discrete distributions:
- Geometric and its properties
- Coupon Collector Part I
LLM 19.5.4
TJ
20 Thu, Apr 04 Discrete distributions:
- Negative Binomial
- Coupon Collector Part II
- Reservoir Sampling

Slides with notes
Wikipedia
Stand-up Maths
hw09 out TJ
21 Tue, Apr 09 Markov inequality
Chebyshev inequality

Slides with notes
LLM 20.1
LLM 20.2
P 6.2.2
TJ
22 Thu, Apr 11 Applications of Markov and
Chebyshev's inequalities
Continuous Uniform Distribution

Slides with notes
LLM 20.1.1
LLM 20.2.1
hw10 out TJ
23 Tue, Apr 16 Normal Distribution
Exponential Distribution
LLM 20.2.2
P 4.2.3
TJ
24 Thu, Apr 18 Poisson Distribution P 4.2.2
P 11.1.2
HW 11 out TJ
25 Tue, Apr 23 Poisson Process
Slides with notes
P 11.1.2 TJ
26 Thu, Apr 25 Probability in Algorithms:
- Bucket Sort
CLRS 8.4
Final Practice Problems out TJ
27 Tue, Apr 30 Final exam review Final Practice Solutions out TJ
Thu, May 02 Study period begins
TBA Final Exam
Any day from May 6 to May 10
Cumulative and covers all topics

Textbooks

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.

Participation

  • Participation will be tracked with Piazza polls.
  • You will get the full participation points if you answer at least 75% of the possible Piazza polls.
  • If you end up answering x% Piazza polls, where x < 75, you will get x/75 of the 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.

Homework

  • Weekly homework assignments will be posted on Thursdays.
  • Assignments will be due Wednesdays by 09:00 p.m. ET, electronically via Gradescope.
  • Gradescope will remain open for a 3-hour grace period after the posted deadline.
  • Late assignments will not be accepted after the grace period as we intend to post solutions the following day.
  • You can use up to 5 grace periods without penalty, after that, you will receive a 10% penalty on each future late submission.
  • Students who used no more than 2 grace periods will receive a 5% extra credit towards their overall homework score.
  • The lowest grade on your homework assignments will be dropped.
  • 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.
  • Select the right pages on Gradescope for each problem (solved or not) to avoid a small homework penalty.
  • Submissions with identically worded answers, including identical pseudocodes, are considered serious offence and will be reported to Dean's Office.
  • Any use of ChatGPT or similar AI functionality to help solve homework problems violates 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.

Exams

  • 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.

Grading

The course grade will break down as follows:
  • 5% participation with Piazza polls
  • 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.

Miscellaneous

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: