Boston University - Summer 2024
CAS CS 237S - Probability in Computing
Instructors and Course Staff
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.
- 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 |
Mon, Jul 01 |
Course information, Tips to succeed
Verifying polynomials, Random experiments
Sample spaces, events
|
LLM 17.1 - 17.2
P 1.1 - 1.2
|
Collaboration &
Honesty Policy
Lab 1: Lecture 1
|
| 2 |
Tue, Jul 02 |
Probability function
Probability axioms and rules.
Computing probabilities
|
LLM 17.3
LLM 17.5
P 1.3
P 2
|
Last day to drop
without a “W”
|
| 3 |
Wed, Jul 03 |
Tree diagrams
Monty Hall problem
|
P 3.1.1 - 3.1.3
P 3.1.6
P 3.2.1
P 4.0 - 4.1
|
Lab 2: Lecture 2
Non-transitive Dice
Video
HW1 out (Thu)
|
| 4 |
Mon, Jul 08 |
Continuous Probability Spaces
Anomalies with Continuous Probability
Random variables
|
LLM 19.1
LLM 19.3
LMM 18.2 - 18.5
LLM 18.7
P 1.4.0
|
Lab 3: Lectures 3 & 4
|
| 5 |
Tue, Jul 09 |
Probability Mass Function
Probality Density Function
Cummulative Distribution Function
|
LLM 18.7
LLM 18.9
P 1.4.2
P 1.4.3
|
HW1 due (Tue)
Card game: higher or lower?
|
| 6 |
Wed, Jul 10
|
Conditional probability
Product rule
Law of total probability
Independent events
Bayes' Rule
|
LLM 18.8
LLM 19.2
P 1.4.3
P 3.1.4
|
Lab 4: Lecture 5
Midterm Practice Problems (out)
HW2 out (Thu)
|
| 7 |
Mon, Jul 15 |
Pairwise Independence
Mutual independence
Midterm Review
|
P 1.4.1
|
Lab 5: Lectures 6 & 7
Practice solutions
|
| -- |
Tue, Jul 16 |
Midterm - from 1:30pm to 3:30pm
|
Everything
so far
|
HW2 due (Tue)
|
| 8 |
Wed, Jul 17 |
People versus Collins
Independence of random variables
Expected value of a random variable
|
To be defined
|
Lab 6: Lecture 8
HW3 out (Thu)
|
| 9 |
Mon, Jul 22 |
Infinity sums
Linearity of expectation
Indicator Random Variables
Law of the Unconscious Statistician (LOTUS)
|
LLM 19.4-19.5
P 3.2.2
P 6.1.2
|
Lab 7: Lecture 9
Last day to drop
with a “W”
|
| 10 |
Tue, Jul 23 |
Expectation of continuous random variables
Conditional expectation
Law of Total Expectation
|
LLM 20.2
LLM 20.3
|
Lab 8: Lecture 10
|
| 11 |
Wed, Jul 24 |
Linearity of conditional expectation
Variance
Standard deviation
Variance properties
|
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 |
Mon, Jul 29 |
Discrete distributions:
Bernoulli, Uniform,
Binomial, Geometric,
Negative Binomial
|
LLM 20.1
LLM 20.2
LLM 20.3.5
LLM 20.4
|
Lab 9: Lectures 11 and 12
HW3 due (Thu)
HW4 out (Fri)
|
| 13 |
Tue, Jul 30 |
Coupon Collector
Reservoir Sampling
|
P 4.2.2
P 4.2.3
P 11.1.2
|
Lab 10: Lecture 13
|
| 14 |
Wed, Jul 31 |
Estimation by sampling
Markov inequality
Chebyshev inequality
Applications of Markov and
Chebyshev's inequalities
|
CLRS 5
|
Final Exam
Practice Solutions (out)
|
| 15 |
Mon, Aug 5
|
Continuous distributions:
Uniform, Normal
Exponential
|
CLRS 11
|
Lab 11: Lectures 14 & 15
HW4 due (Thu)
Practice solutions (Fri)
|
| 16 |
Tue, Aug 06 |
Discrete Distribution:
- Poisson and Poisson process
Probability in algorithms
- Bucket Sort
|
Everything
so far
|
Solving Practice Problems
|
| -- |
Wed, Aug 07 |
Final - from 1:30pm to 3:30pm
|
|
No lab section
Last day of class
|
Textbooks
You can access both books for free or support the authors by purchasing the books.
Keep in mind:
- 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 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 Vjudge
- Students must attend at least 75% of both lectures and discussion labs to pass the course.
- If you end up geting x% of the points, where x < 75, you will get x/75 of the points.
Homework
- There will be weekly homework assignments posted on Thursdays mornings.
- Assignments will be due Wednesdays by 09:00PM 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.
- Students who used no more than 1 grace period will receive a 5% extra credit towards their overall homework score.
- 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 5% penalty for each non-selected problem.
- 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 lasts 120 minutes and their locations will be 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
- 25% weekly homework assignments
- 35% in-class midterm exam
- 35% in-class final exam
- Students must pass both exams with at least 40% of the grade 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:
