$\DeclareMathOperator{\p}{Pr}$ $\DeclareMathOperator{\P}{Pr}$ $\DeclareMathOperator{\c}{^C}$ $\DeclareMathOperator{\or}{ or}$ $\DeclareMathOperator{\and}{ and}$ $\DeclareMathOperator{\var}{Var}$ $\DeclareMathOperator{\E}{E}$ $\DeclareMathOperator{\std}{Std}$ $\DeclareMathOperator{\Ber}{Bern}$ $\DeclareMathOperator{\Bin}{Bin}$ $\DeclareMathOperator{\Poi}{Poi}$ $\DeclareMathOperator{\Uni}{Uni}$ $\DeclareMathOperator{\Exp}{Exp}$ $\DeclareMathOperator{\N}{N}$ $\DeclareMathOperator{\R}{\mathbb{R}}$ $\newcommand{\d}{\, d}$

CS109 Midterm 1
Monday, July 13th, in-class

Logistics

The first CS109 midterm is a 75-minute, closed book, closed calculator/computer exam. You are, however, allowed to bring 3 pages (front and back) of notes in the exam, written by hand with a pen or pencil (no iPad writing, please). Make sure to practice before the exam.

Where to Go

The exam location is in the regular classroom, CoDa B80

Coverage

The midterm puts special emphasis on the material from the first two problem sets. This includes material in lecture up to and including class on Wednesday, July 8th.

Answer Format

You are going to be solving probability questions by hand. To that extent we are not interested in numeric answers, but rather in formulaic answers. It is fine for your answers to include summations, products, factorials, exponentials, and combinations, unless the question specifically asks for a numeric quantity or closed form. Where numeric answers are required, the use of fractions is fine. You must show your work. Any explanation you provide of how you obtained your answer can potentially allow us to give you partial credit for a problem. For example, describe the distributions and parameter values you used, where appropriate.

Problems Fair Game for Midterm 1

You are responsible for material from Lectures 1–10 (through Probabilistic Models). The old midterms cover a range of topics, and some of them include problems that use material we have not yet covered. This guide lists, for each exam, which problems are fair game and which you should skip. Exams are listed newest first.

In scope (Lectures 1–10)

Counting and combinatorics; axioms of probability; conditional probability and Bayes’ theorem for discrete events; independence and conditional independence; discrete random variables (Bernoulli, Binomial, Geometric, Negative Binomial, Poisson); expectation, variance, and moments (including linearity of expectation and indicator variables); continuous random variables (Uniform, Exponential); the Normal/Gaussian distribution (including the normal approximation to the binomial and the Poisson); and joint distributions and probabilistic models (joint and marginal distributions, covariance, adding random variables, sums of independent Gaussians).

Not in scope: Bayesian inference — computing a posterior or updated belief over an unknown, model or hypothesis selection, and any inference that uses a continuous likelihood. Ordinary Bayes’ theorem for discrete events (Lecture 2) is still fair game; what is excluded is the Lecture 11 material of updating a full belief distribution. Also out of scope, as before: Beta distributions, the Central Limit Theorem, and sampling-based estimation.

Unless a specific part is flagged below, every problem on the exam is fair game.

Winter 2026 (PDF [Soln])

Fair game except where noted.

  1. Literary Randomness — Poisson, Normal, exponential
  2. Art Museum Security Code — counting
  3. Fraud Detection — Bayes’ theorem (discrete), conditional independence
  4. Let There Be Light — Poisson, variance
  5. Footprints in the Caves of Lascaux — part (a) is fair game (a Normal probability). Skip part (b): it asks for a posterior belief over height (inference).
  6. TicketWizard — normal approximation to the binomial, Poisson

Fall 2025 (PDF [Soln])

Fair game except where noted.

  1. Counting Rain Drops — Poisson, truncated Poisson
  2. Vibrant Variables — parts (b) and (c) are fair game (Normal/binomial, Poisson). Skip part (a): it asks for the variance of a Beta posterior.
  3. Word Identification — SKIP. Bayesian inference (posterior over words).
  4. Variance Reduction Sampling — parts (a)–(c) are fair game (Bernoulli, expectation, variance). Skip part (d): the distribution of a sample average (Central Limit Theorem).
  5. Outlier Detection for Code in Place — SKIP. Bayesian inference with continuous likelihoods.
  6. Random Molecules — independence, indicator variables, expectation
  7. The Golden Coin — geometric and binomial

Winter 2025 (PDF [Soln])

Fair game except where noted.

  1. What a Time to Be Alive — Poisson, Bernoulli, normal approximation, law of total probability
  2. Vibrant Variables — Poisson, exponential, uniform
  3. Board Game Analysis — probability, expectation, variance
  4. Rival Production — part (a) is fair game (a probability calculation). Skip parts (b) and (c): they build a posterior belief over N (inference).
  5. Accidental Caps-Lock Press — part (a) is fair game (a Normal probability). Skip parts (b) and (c): they infer a posterior from a continuous observation.
  6. The Large Language Model That Keeps on Trying — geometric, conditional probability

Fall 2024 (PDF [Soln])

Fair game except where noted.

  1. Adventure is Out There — Bernoulli, Bayes’ theorem (discrete), expectation
  2. Chance Encounters — modeling with geometric, Poisson, Poisson-binomial, normal approx
  3. Bingo! — counting
  4. The Driftwood Random Variable — custom discrete RV, normalizing constant, E and Var
  5. True Random — Normal, inverse Φ
  6. DNA Mutation Clock — parts (a), (b), and (d) are fair game (Poisson, binomial, probability). Skip part (c): it builds a posterior belief over the number of years (inference).

Fall 2023 (PDF [Soln])

Fair game except where noted.

  1. Measure of Variety — probability, Poisson, expectation
  2. GPT Generation — probability, counting, geometric, variance
  3. Era’s Tour — exponential, binomial, Poisson approximation
  4. How Many Coin Flips? — SKIP. Bayesian inference (posterior over the number of flips).
  5. Auto Morse Code Detection — parts (a) and (b) are fair game (a Normal probability; computing a prior). Skip parts (c) and (d): they infer a posterior from a continuous observation.

Fall 2022 (PDF [Soln])

Fair game except where noted.

  1. Weather Prediction — estimating probability from data, independence
  2. Down to Lunch — Poisson, binomial
  3. Random Edges — counting, PMF, variance
  4. Expressed Trait — Poisson
  5. Mixing up Gaussians — part (a) is fair game (a law-of-total-probability calculation). Skip part (b): it infers a posterior from a continuous observation.
  6. Bayesian Viral Load Test — parts (a) and (b) are fair game (probability, Poisson approximation). Skip part (c): it builds a posterior belief over the viral load (inference).

Winter 2022 (PDF [Soln])

Fair game except where noted.

  1. Stanford Life — independence, Poisson
  2. Midterm Theory — conditional probability
  3. Algorithmic Analysis — counting
  4. ASL Fingerspelling — conditional probability, independence
  5. Binary Spoof — binomial, Bayes’ theorem (discrete)
  6. PSetApp Answer Checker — part (a) is fair game (a Normal probability). Skip part (b): it infers a posterior from a continuous observation.
  7. Beyond the Binomial — Poisson-binomial (different p per trial)

Fall 2021 (PDF [Soln])

Fair game except where noted.

  1. Color.com — counting, binomial, Poisson approximation
  2. Doodle Poll — binomial, independence
  3. I Heard That! — only part (d) is fair game (a Normal probability). Skip parts (a)–(c): they update a belief about whether the baby can hear (inference).
  4. Sleep and Dreams — Poisson, expectation, exponential, uniform
  5. Longest Sequence of Heads — counting, PMF, recursion

Spring 2019 (PDF [Soln])

Fair game except where noted.

  1. Enigma Machine — counting
  2. Daycare.ai — binomial, expectation
  3. µ Girls — exponential, Poisson process, independence
  4. Name2Age — SKIP. Bayesian inference (posterior over birth year).
  5. Grades are not Normal — parts (a)–(c) are fair game (Normal and given-density probabilities). Skip part (d): Bayesian model selection.

Fall 2018 (PDF [Soln])

Fair game except where noted.

  1. Random Writer — counting, binomial
  2. Race Condition — Poisson
  3. Algorithmic Fairness — joint probability table, marginal/conditional probability
  4. Traffic Light — continuous RV, expectation, variance, uniform
  5. Drug Effectiveness — part (a) is fair game (Bayes’ theorem with a discrete observation). Skip part (b): it infers a posterior from a continuous (Gaussian) observation.
  6. Simulation Accuracy — normal approximation to a binomial proportion

Fall 2017 (PDF [Soln])

Fair game except where noted.

  1. Alpha TicTacToe — counting, probability
  2. Wisdom of the Crowds — binomial, normal approximation
  3. 500 year floodplanes — Poisson
  4. Gaussian Mixture Model — parts (a)–(c) are fair game (Normal probabilities, law of total probability). Skip part (d): it infers which species from a continuous observation.
  5. Curse of Dimensionality — uniform, independence
  6. Goodbye integral (Monte Carlo Integration) — SKIP. Sampling-based estimation, covered after the midterm.

Spring 2017 (PDF [Soln])

Fair game except where noted.

  1. Spotify — counting, probability
  2. Secure Passwords — counting, geometric, expectation
  3. Shazam — counting, binomial, Bayes’ theorem (discrete)
  4. Recaptcha — parts (a) and (b) are fair game (a Normal probability; a uniform PDF). Skip part (c): it infers a posterior from a continuous observation.
  5. Exponentials — exponential distribution, CDF of a max
  6. Eleven-eleven — Poisson, normal approximation, probit function

Spring 2016 (PDF [Soln])

Fair game except where noted.

  1. Card game — counting, probability, expectation
  2. Sampling a median — counting, binomial
  3. Netflix Tearjerker — conditional independence, Bayes’ theorem (discrete)
  4. Wind energy — Normal, normal approximation to the binomial, sum of Gaussians
  5. Autonomous car — SKIP. Bayesian inference for a continuous quantity (posterior PDF).
  6. Ride sharing — Poisson, expectation, exponential

What about the Phi table? I am not going to make you look up values from a phi table. Instead you can leave your answer in terms of phi (the CDF of the standard normal). For example $\Phi(\frac{3}{4})$ is a fine final answer. This was not the case in the past so you will see questions which ask for a numeric answer in the practice exams.

Essential Practice

We recommend working through at least one practice midterm exam under realistic conditions (timed) before you take the midterm. Note: You should not expect that a TA will have prepared to answer these problems in office hours (there are far too many for them to prep them all). If you ask about one of this problems on the Ed forum or in office hours please be ready to give the full context, and be aware that the TA might not be able to prioritize them. This is especially true if you ask about them more than a week before the exam.

Also note that different content has been emphasized in prior quarters. So there may be questions on these exams that will cover content not emphasized in this quarter of CS109. Feel free to ask on Ed if you want to double check about any topics.

Extra Practice


'