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

Instructors and Course Staff

Name	Office Hours
Prof. Alina Ene	Google Calendar
Prof. Tiago Januario
Teaching Fellow: Ta Duy Nguyen
Teaching Assistants: Champ Laksanawisit, Jessica Nguyen, Jiawei Sun, Noah Barnes, Oscar Mo, and Steve Choi
Course Assistants: Daniel Matuzka, Eytan Mobilio, Jerry Lin, Jude Cudiamat Lopez, Letitia Caspersen, Michael Krah, Mohnish Shridhar, Sarah Yuhan, and Vi Tjiong

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

• CS 131 - Combinatoric Structures
• MA 123 - Calculus I
• CS 111 - Introduction to Computer Science I

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

Structure

• A 75 minutes lecture taught by one Instructor
  • Section A: HAR105, Tuedays and Thursdays, from 2:00pm to 3:15pm
• 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.

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	Tue, Sep 03	Course information, Tips to succeed Random experiments	P 1.1 P 1.2 OB 1B	Google Colab Collaboration & Honesty Policy	TJ
2	Thu, Sep 05	Sample spaces, events Probability function	LLM 17.1 P 1.3.1-1.3.3	HW1 out	AE
3	Tue, Sep 10	Probability axioms and rules Computing probabilities	LLM 17.3 LLM 17.5 P 2	Non-transitive Dice Video	TJ
4	Thu, Sep 12	Tree diagrams The Monty Hall problem	LLM 17.2 LLM 18.1.2	HW2 out	TJ
5	Tue, Sep 17	Continuous Probability Spaces Anomalies with Continuous Probability	P 1.3.5	Video	TJ
6	Thu, Sep 19	Random variables Definition and examples	LLM 19.1 P 3.1.1 P 4.1.0	HW3 out	TJ
7	Tue, Sep 24	Distribution Functions 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	TJ
8	Thu, Sep 26	Properties of PDFs and CDFs Conditional probability	P 3.1.6 P 4.1.4	HW4 out	TJ
9	Tue, Oct 01	Product rule Law of total probability	LLM 18 P 1.4.0	Game: higher or lower?	TJ
10	Thu, Oct 03	Bayes' Rule	P 1.4.2 P 1.4.3 3Blue1Brown Veritasium	HW5 out	AE
11	Tue, Oct 08	Independent events Pairwise Independence Mutual independence	LLM 18.7 LLM 18.8		AE
12	Thu, Oct 10	People versus Collins Independence of random variables	LLM 18.9 P 1.4.1 Video	HW6 out	AE
Tue, Oct 15		Monday Schedule
13	Thu, Oct 17	Expected value of a random variable Infinite sums	LLM 19.4 P 3.2.2	Practice Problems out HW7 out	TJ
14	Tue, Oct 22	Expectation of continuous random variables Linearity of Expectation	LLM 19.5 P 6.1.2	Practice Problems Solution out	TJ
Thu, Oct 24		In Class Midterm
15	Tue, Oct 29	Law of the unconscious statistician Conditional expectation	LLM 19.4.1 P 3.2.3 LLM 19.4.6		TJ
16	Thu, Oct 31	Law of total expectation Linearity of conditional expectation	LLM 19.4.1 P 3.2.3 LLM 19.4.6	HW8 out	TJ
17	Tue, Nov 05	Variance Standard deviation Variance properties	LLM 20.3 P 3.2.4	Video	TJ
18	Thu, Nov 07	Discrete distributions: - Bernoulli, - Uniform, - Binomial	LLM 19.3.1 LLM 19.3.2 P 3.1.5	HW9 out	TJ
19	Tue, Nov 12	Discrete distributions: - Negative Binomial - Geometric and its properties	LLM 19.5.4		TJ
20	Thu, Nov 14	Coupon collector's problem	Stand-up Maths	HW10 out	TJ
21	Tue, Nov 19	Reservoir Sampling Estimation by sampling	Wikipedia Lecture notes		TJ
22	Thu, Nov 21	Markov inequality Chebyshev inequality	LLM 20.1 LLM 20.2 P 6.2.2	Final Practice Problems out	AE
23	Tue, Nov 26	Applications of Markov and Chebyshev's inequalities	LLM 20.1.1 LLM 20.2.1 LLM 20.2.2		AE
Thu, Nov 28		Thanksgiving break
24	Tue, Dec 03	Normal Distribution	P 4.2.3	HW11 out on Dec 02	AE
25	Thu, Dec 05	Exponential distribution	P 4.2.2	Final Practice Solutions out	AE
26	Tue, Dec 10	Poisson Distribution Poisson Process Course evaluation	P 11.1.2 LLM 21.1 LLM 21.2	HW11 due on Dec 09	AE
27	Wed, Dec 11	Study Period begins
Tue, Dec 17		Final Exam, from 3:00pm – 5:00pm HAR105 - Regular time room (2-hours exam) IECB12 - Extended time room for students with accommodation letters

Textbooks

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

• (LLM) Mathematics for Computer Science by Eric Lehman, Tom Leighton, and Albert Meyer.
• (P) Introduction to Probability, Statistics, and Random Processes by Hossein Pishro-Nik.
• (CLRS) Cormen, Leiserson, Rivest, and Stein. Introduction to Algorithms, Fourth Edition, MIT Press.

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. Provide step-by-step explanations, not just answers. Answers without explanations will earn a small fraction of the points.
• 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.
• Each no submission will be tread as a late submission.
• You can use up to 5 grace periods without penalty, after that, you will receive a 1% penalty on each future late submission.
• The lowest grade on your homework assignments will be dropped, after applying the penalties.
• You are responsible for submitting one single PDF file with high-quality images of your solutions. Illegible submissions will receive a 0 grade
• We highly recommend Dropbox to scan your homework before uploading it.
• Select the correct pages on Gradescope for each problem (solved or not) to avoid a 10% homework penalty. In cases where you do not have a solution to submit for a specific problem, type a brief note such as "No solution provided".
• 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% 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.

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: