Boston University - Summer 2025
CAS CS 237S - Probability in Computing

Instructors and Course Staff

Name	Office Hours
Prof. Tiago Januario	Google Calendar
Teaching Fellow: Erick Jimenez

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.

	Date	(Tentative) Topics	Reading	Handouts/Homework/Notes	Instructor
Lec. 01	Tue, May 20	Course information, Tips to succeed Random experiments Sample spaces, events Probability function	P 1.1 P 1.2 OB 1B	Google Colab Collaboration & Honesty Policy LLM 17.1 P 1.3.1-1.3.3	TJ
Lec. 02	Wed, May 21	Probability axioms and rules Computing probabilities Tree diagrams The Monty Hall problem	LLM 17.3 LLM 17.5 P 2 LLM 17.2 LLM 18.1.2	Non-transitive Dice Video	TJ
Lab. 01	Thu, May 22	The lab reinforces lecture content through hands-on engagement and collaborative learning with interactive examples and problem-solving related to the topics covered in the previous lectures.	Review all recommended readings before lab.	hw01 out	EJ
Mon, May 26		Classes at Boston University are suspended on Monday, May 26, 2025, due to Memorial Day
Lec. 03	Tue, May 27	Continuous Probability Spaces Anomalies with Continuous Probability Random variables Sum of random variables Definition and examples Distribution Functions Probality Density Function Cummulative Distribution Function	P 1.3.5 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	Video	TJ
Lec. 04	Wed, May 28	Properties of PDFs and CDFs Examples and applications. Functions of random Variables Conditional probability Chain rule	P 3.1.6 P 4.1.4 LLM 18 P 1.4.0	hw01 due today by 9:00 PM Video Game: higher or lower?	TJ
Lab. 02	Thu, May 29	The lab reinforces lecture content through hands-on engagement and collaborative learning with interactive examples and problem-solving related to the topics covered in the previous lectures.	Review all recommended readings before lab.	hw02 out	EJ
Lec. 05	Fri, May 30	Law of total probability Bayes' Rule Independent events Pairwise Independence Mutual independence	P 1.4.2 P 1.4.3 3Blue1Brown Veritasium LLM 18.7 LLM 18.8	Monday Schedule	TJ
Lec. 06	Mon, Jun 02	People versus Collins Independence of random variables Expected value of a random variable Infinite sums	LLM 18.9 P 1.4.1 LLM 19.4 P 3.2.2	Video	TJ
Lec. 07	Tue, Jun 03	Expectation of continuous random variables Linearity of Expectation Law of the unconscious statistician Conditional expectation Law of total expectation Linearity of conditional expectation	LLM 19.5 P 6.1.2 LLM 19.4.1 P 3.2.3 LLM 19.4.6		TJ
Lab. 03	Wed, Jun 04	Midterm review based on the midterm practice problems.	Review all midterm practice problems readings before lab.		EJ
Thu, Jun 05		Midterm, in class, during lab time		Covers all topics up to independence. hw03 out
Lec. 08	Mon, Jun 09	Variance Standard deviation Variance properties Discrete distributions: - Bernoulli, - Uniform, - Binomial	LLM 20.3 P 3.2.4 LLM 19.3.1 LLM 19.3.2 P 3.1.5	Video	TJ
Lec. 09	Tue, Jun 10	Discrete distributions: - Geometric and its properties - Coupon Collector - Negative Binomial	LLM 19.5.4 Wikipedia Stand-up Maths		TJ
Lec. 10	Wed, Jun 11	Markov inequality Chebyshev inequality Applications of Markov and Chebyshev's inequalities Continuous Uniform Distribution	LLM 20.1 LLM 20.2 P 6.2.2 LLM 20.1.1 LLM 20.2.1		TJ
Lab. 04	Thu, Jun 12	The lab reinforces lecture content through hands-on engagement and collaborative learning with interactive examples and problem-solving related to the topics covered in the previous lectures.	Review all recommended readings before lab.	hw04 out	EJ
Lec. 11	Mon, Jun 16	Normal Distribution Exponential Distribution	LLM 20.2.2 P 4.2.3 P 4.2.2 P 11.1.2		TJ
Lec. 12	Tue, Jun 17	Poisson Process Poisson Distribution	P 11.1.2		TJ
Lec. 13	Wed, Jun 18	Applied probability: - Bucket Sort - Reservoir Sampling	CLRS 8.4		TJ
Thu, Jun 19		Classes at Boston University are suspended on Thursday, June 19, 2025, due to Juneteenth Holiday		hw05 out
Lec. 14	Mon, Jun 23	Central Limit Theorem Law of Large Numbers			TJ
Lec. 15	Tue, Jun 24	Chernoff bounds			TJ
Lab. 05	Wed, Jun 25	Final exam review section!	Review all homework assignments beforehand.		EJ
Thu, Jun 26		Final exam, in class, during lab time		Covers all topics.

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 85% of the possible Piazza polls.
• If you end up answering x% Piazza polls, where x < 85, you will get x/85 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 2 grace periods without penalty, after that, you will receive a 10% 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 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.
• We highly recommend Dropbox to scan your homework before uploading it.
• 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 and last homework).
• 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
• 25% weekly homework assignments
• 35% in-class midterm exam
• 35% in-class final exam.
• 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

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.