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


Instructors and Course Staff

Name Office Hours Office
Prof. Tiago Januario CDS 1001, Thu, 1:30-3:30pm CDS 911
Teaching Fellow: Timothy Jackman CDS 364, Tue, 4:00-5:00pm
CDS 1001, Thu, 12:00-1:00pm
CDS 1010

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

Prerequisites

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

Structure:

  • Three 150 minutes lectures taught by a Professor
    • At CDS364, on Mondays, Tuesdays, and Wednesdays, from 1:30pm to 4:00pm
  • Two 60 minute discussion labs taught by a Teaching Fellow
    • At CDS364, on Mondays and Wednesdays, from 4:00pm to 5:00pm
  • Attendance in lectures and discussion is mandatory
Additionally, every member of the course staff will hold office hours. The purpose of the office hours is to answer questions on any aspect of the course material and lab or homework problems.

Discussion Labs
Discussion labs cover an invaluable part of the course:

  • Tips on homework questions
  • Supplemental material not covered in lecture
  • Interactive problem-solving sessions
We will post lab notes on Piazza in advance -- please read them before coming to the lab. Lab solutions will be posted after all discussion labs conclude.

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
1 Wed, Jul 05 Course information, Tips to succeed
Verifying polynomials, Random experiments
Sample spaces, events
Slides with notes 		LLM 17.1 - 17.2
P 1.1 - 1.2
 Collaboration &
Honesty Policy
Lab 1: Lecture 1
HW1 out (Fri)
2 Mon, Jul 10 Probability function
Probability axioms and rules.
Computing probabilities
Slides with notes 		LLM 17.3
LLM 17.5
P 1.3
P 2
 Lab 2: Lecture 2
Non-transitive Dice
Video
3 Tue, Jul 11 Tree diagrams
Monty Hall problem
Continuous Probability Spaces
Anomalies with Continuous Probability
Slides with notes 		P 3.1.1 - 3.1.3
P 3.1.6
P 3.2.1
P 4.0 - 4.1 		Last day to drop
without a “W”
4 Wed, Jul 12 Random variables
Probability Mass Function
Probality Density Function
Cummulative Distribution Function
Slides with notes 		LLM 19.1
LLM 19.3
LMM 18.2 - 18.5
LLM 18.7
P 1.4.0
 Lab 3: Lectures 3 & 4
HW1 due (Thu)
HW2 out (Fri)
5 Mon, Jul 17 Conditional probability
Product rule
Law of total probability
Slides with notes 		LLM 18.7
LLM 18.9
P 1.4.2
P 1.4.3 		Lab 4: Lecture 5
Card game: higher or lower?
6 Tue, Jul 18 Independent events
Bayes' Rule
Slides with notes 		LLM 18.8
LLM 19.2
P 1.4.3
P 3.1.4 		Midterm Practice
Problems (out)
7 Wed, Jul 19 Pairwise Independence
Mutual independence
Slides with notes 		P 1.4.1
 Lab 5: Lectures 6 & 7
HW2 due (Thu)
Practice solutions
8 Mon, Jul 24 People versus Collins
Independence of random variables
Midterm Review
Slides with notes 		Everything
so far
-- Tue, Jul 25 Midterm - from 1:30pm to 3:30pm
PHO 203 - Photonics Building 		No lab section
9 Wed, Jul 26 Expected value of a random variable
Infinity sums
Linearity of expectation
Slides with notes 		LLM 19.4-19.5
P 3.2.2
P 6.1.2 		Lab 6: Lecture 9
HW3 out (Fri)
Last day to drop
with a “W”
10 Mon, Jul 31 Expectation of continuous random variables
Conditional expectation
Law of Total Expectation
Linearity of conditional expectation
Slides with notes 		LLM 20.2
LLM 20.3 		Lab 7: Lecture 10
11 Tue, Aug 1 Variance
Standard deviation
Variance properties
Discrete distributions:
Bernoulli, Uniform,
Binomial, Geometric,
Negative Binomial
Slides with notes 		A game to
play everyday
P 3.1.5
LLM 19.4.6
LLM 19.5.4
Probability
distributions 		Final Exam
Practice Problems (out)
12 Wed, Aug 2 Coupon Collector
Reservoir Sampling
Slides with notes 		LLM 20.1
LLM 20.2
LLM 20.3.5
LLM 20.4
Lab 8: Lectures 11 and 12
HW3 due (Thu)
HW4 out (Fri)
13 Mon, Aug 7 Estimation by sampling
Markov inequality
Chebyshev inequality
Applications of Markov and
Chebyshev's inequalities
Slides with notes 		P 4.2.2
P 4.2.3
P 11.1.2 		Lab 9: Lecture 13
14 Tue, Aug 8 Continuous distributions:
Uniform, Normal
Exponential
Slides with notes 		CLRS 5 Final Exam
Practice Solutions (out)
15 Wed, Aug 9 Discrete Distribution:
- Poisson and Poisson process
Probability in algorithms
- Bucket Sort
Slides with notes 		CLRS 11 Lab 10: Lectures 14 & 15
HW4 due (Thu)
Practice solutions (Fri)
16 Mon, Aug 14 Probabilistic Data Structures:
- Bloom Filters
Sublinear-time Algorithms
Review 		Everything
so far 		Solving Practice Problems
-- Tue, Aug 15 Final - from 1:30pm to 3:30pm
PHO 203 - Photonics Building 		No lab section
Last day of class

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 contact the instructor (and forward any relevant documentation from Disability and Access Services) in a timely manner.
  • 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 or student groups.

Attendance and participation

  • Attendance will be tracked with Canvas
  • 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.
  • 80% of the points are for participation and the remaining 20% is for correctness.
  • You will get the full 4% of the course grade if you get at least 80% 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: https://tophat.com/students/
Join Code: 258641

Homework

  • There will be weekly homework assignments posted on Fridays.
  • Assignments will be due Thursday by 11:59PM 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.
  • Your homework grade will be calculated by a weighted arithmetic mean.
  • Each homework contributes equally to the homework average with weight 2, except the one with the lowest grade.
  • The lowest grade on your homework assignments will contribute with weight 1.
  • Submissions with identical worded answers, including identical pseudocode, will receive no grade.
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 lasts 120 minutes 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:
  • 4% class attendance and participation with Top Hat
  • 1% Piazza “good questions” and “good answers”
  • 30% weekly homework assignments
  • 30% in-class midterm exam
  • 35% in-class final exam
  • Students must pass both exams with at least 45% of the grade (in average) to pass the course.
  • 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 class.

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: