$\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 2
Tuesday, August 4th, in-class

Logistics

The second CS109 midterm is a 75-minute, closed book, closed calculator/computer exam. You are, however, allowed to bring 5 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

Midterm 2 is cumulative, but it puts special emphasis on the material we have covered since Midterm 1, which is the material in problem sets 4 and 5. You are responsible for material in lecture up to and including class on Wednesday, July 22nd (Lecture 18, Information Theory). Maximum likelihood estimation (Lecture 19) and everything after it will not be on this exam.

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 2

Midterm 2 is cumulative: you are responsible for material from Lectures 1–18 (through Information Theory), with special emphasis on the material we have covered since Midterm 1 (Lectures 13–18, problem sets 4 and 5).

Because the exam now covers everything through Information Theory, every problem on every old midterm is fair game — including the Bayesian inference, Beta, and Central Limit Theorem parts that you were told to skip before Midterm 1. The old finals are where you will find practice on the newer material, but finals also cover topics we have not reached yet, so the guide below tells you which final problems to do and which to skip.

In scope (Lectures 1–18)

Counting and combinatorics; axioms of probability; conditional probability and Bayes’ theorem; independence and conditional independence; discrete random variables (Bernoulli, Binomial, Geometric, Negative Binomial, Poisson, Hypergeometric); expectation, variance, and moments (linearity of expectation, indicator variables); continuous random variables (Uniform, Exponential); the Normal/Gaussian distribution (including the normal approximation to the binomial and the Poisson); joint distributions and probabilistic models (covariance, adding random variables, sums of independent Gaussians); Bayesian inference (posteriors over a discrete or continuous unknown, model selection); the Multinomial distribution; the Beta distribution and Beta posteriors; the Central Limit Theorem and the distribution of a sample mean; bootstrapping and p-values; probabilistic analysis of algorithms; and information theory (entropy, conditional entropy, and mutual information).

Out of scope (Lecture 19 and later) — you do NOT need these

Maximum likelihood estimation (MLE) and MAP parameter estimation; Naive Bayes; logistic regression; model accuracy, calibration, and classifier comparison; and deep learning. Several final exam problems are entirely about these topics, and several others have one part that is; both are flagged below.

Unless a specific part is flagged, every problem listed below is fair game.

Part 1: Old Midterms

All problems on all of the old midterms are fair game. The topic tags below are there to help you find targeted practice. Exams are listed newest first.

Winter 2026 (PDF [Soln])

  1. Literary Randomness — Poisson, Normal, exponential
  2. Art Museum Security Code — counting
  3. Fraud Detection — Bayes’ theorem, conditional independence
  4. Let There Be Light — Poisson, variance
  5. Footprints in the Caves of Lascaux — Normal, Bayesian inference
  6. TicketWizard — normal approximation to the binomial, Poisson

Fall 2025 (PDF [Soln])

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

Winter 2025 (PDF [Soln])

  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 — Bayesian inference (a version of the German-tank problem)
  5. Accidental Caps-Lock Press — Normal, Bayesian inference
  6. The Large Language Model That Keeps on Trying — geometric, conditional probability

Fall 2024 (PDF [Soln])

  1. Adventure is Out There — Bernoulli, Bayes’ theorem, expectation
  2. Chance Encounters — geometric, Poisson, Poisson-binomial, normal approximation
  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 — Poisson, binomial, Bayesian inference

Fall 2023 (PDF [Soln])

  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? — Bayesian inference
  5. Auto Morse Code Detection — Normal, Bayesian inference

Fall 2022 (PDF [Soln])

  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 — Normal, law of total probability, Bayesian inference
  6. Bayesian Viral Load Test — Poisson approximation, Bayesian inference

Winter 2022 (PDF [Soln])

  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
  6. PSetApp Answer Checker — Normal, Bayesian inference
  7. Beyond the Binomial — Poisson-binomial (different p per trial)

Fall 2021 (PDF [Soln])

  1. Color.com — counting, binomial, Poisson approximation
  2. Doodle Poll — binomial, independence
  3. I Heard That! — Bayesian inference with a PMF and with a Normal
  4. Sleep and Dreams — Poisson, expectation, exponential, uniform
  5. Longest Sequence of Heads — counting, PMF, recursion

Spring 2019 (PDF [Soln])

  1. Enigma Machine — counting
  2. Daycare.ai — binomial, expectation
  3. µ Girls — exponential, Poisson process, independence
  4. Name2Age — Bayesian inference, conditional independence
  5. Grades are not Normal — Normal, Bayesian model selection

Fall 2018 (PDF [Soln])

  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 — Bayes with discrete and with continuous (Gaussian) evidence
  6. Simulation Accuracy — normal approximation to a binomial proportion

Fall 2017 (PDF [Soln])

  1. Alpha TicTacToe — counting, probability
  2. Wisdom of the Crowds — binomial, normal approximation
  3. 500 year floodplanes — Poisson
  4. Gaussian Mixture Model — Normal, law of total probability, Bayesian inference
  5. Curse of Dimensionality — uniform, independence
  6. Goodbye integral (Monte Carlo Integration) — estimating a quantity by sampling. Now fair game (it is the same idea that underlies bootstrapping), but it is one of the harder problems in this set.

Spring 2017 (PDF [Soln])

  1. Spotify — counting, probability
  2. Secure Passwords — counting, geometric, expectation
  3. Shazam — counting, binomial, Bayes’ theorem
  4. Recaptcha — Normal, uniform PDF, Bayesian inference
  5. Exponentials — exponential distribution, CDF of a max
  6. Eleven-eleven — Poisson, normal approximation, probit function

Spring 2016 (PDF [Soln])

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

Part 2: Old Finals

The old finals are the only place to find practice problems on the Multinomial, the Beta, the Central Limit Theorem, bootstrapping and p-values, and information theory. Two things to keep in mind:

  • A final is a three-hour, 180-point exam, so a single final has far more problems than you will see on our 75-minute midterm, and the individual problems tend to be longer.
  • Finals cover MLE, Naive Bayes, and logistic regression, none of which are on Midterm 2. Those problems are flagged SKIP below.

Finals also ask you to write pseudocode more often than midterms do. Those problems are still worth doing: writing code to compute a probability, run a bootstrap, or compute an entropy is a good check on whether you understand the math.

Winter 2025 Final (PDF [Soln])

Almost the entire exam is fair game. This is the best single practice exam for the new material.

  1. Short Answer — exponential, Bayes’ theorem, law of total probability, and multinomial (part d)
  2. In-Vitro Fertilization — independence, binomial
  3. Bag of Coins — binomial, law of total probability, Bayesian inference
  4. Microcontroller Precision Error — uniform, Central Limit Theorem
  5. Exponential Backoff — probability, expectation
  6. Indus Valley Script — entropy, conditional entropy, mutual information (an excellent Lecture 18 problem)
  7. Estimating Course Size — expectation and variance of a scaled RV, bootstrapping
  8. Bayesian RNA Sequencing — Poisson, Beta prior and posterior, variance of a Beta
  9. MLE of a Truncated Normal Distribution — SKIP. MLE.
  10. Logistic Regression Conceptual — SKIP. Logistic regression.

Fall 2024 Final (PDF [Soln])

  1. Short Answer — parts (a) and (c) are fair game (exponential; expectation with the law of total expectation). Skip part (b): model accuracy and calibration.
  2. Airline Flights — probability from a table, independence, conditional probability
  3. Board Games — counting, binomial
  4. Song of the Quarter — Central Limit Theorem, difference of two sample means, bootstrapped p-value (all three parts fair game)
  5. What Name Doesn’t Give Away Age? — entropy (Lecture 18)
  6. Hidden Chambers in the Great Pyramid — Poisson, Bayesian inference with a continuous prior
  7. Sorted Random Values — binomial, order statistics, and the Beta distribution
  8. MLE of Negative Binomial — part (a) is fair game (evaluate the Negative Binomial PMF). Skip part (b): MLE.
  9. Recalibrating an Uncalibrated Model — SKIP. Platt scaling / MLE.

Fall 2023 Final (PDF [Soln])

  1. Short Answer — all six parts fair game: exponential; a sum of 1000 uniforms (CLT); mutual exclusivity vs. independence; when the CLT applies; a Beta posterior; Poisson
  2. Don’t Quit Until You Are Ahead — binomial, normal approximation, negative binomial
  3. Popcorn — Normal, conditional probability, law of total probability
  4. Delicate Polling — binomial, expectation, bootstrapping pseudocode
  5. Water Levels — part (a) is fair game (a CDF evaluation). Skip part (b): MLE.
  6. Logistic Regression Priors — SKIP. MAP and logistic regression.
  7. Estimating Child Vocab Size — counting, Bayesian inference over a discrete unknown

Fall 2022 Final (PDF [Soln])

  1. Short Answer — counting, the distribution of a sample mean (CLT), binomial
  2. Machine Learning — SKIP. Logistic regression and Naive Bayes. (Part (b) is really “what is the mean of a Beta posterior?” if you want the practice.)
  3. Night Sight — Poisson, variance, variance of an average
  4. Penalty Shootout — binomial, infinite series, conditioning
  5. Better — Beta posteriors compared by sampling
  6. B-Reel — likelihood of a dataset under two hypotheses, Bayesian model selection, and bootstrapping (all four parts fair game)
  7. Code survival — SKIP. MLE.
  8. Approximate Counting Algorithm — expectation, probabilistic analysis of a randomized algorithm (Lecture 17)

Fall 2021 Final (PDF [Soln])

  1. True or False — parts (a), (c), (d), (e), and (f) are fair game (independence; bootstrapped p-values; the CLT; Poisson vs. exponential; expectation). Skip part (b): it is about the log likelihood function used in MLE.
  2. Algorithmic Art — parts (a), (b), and (c) are fair game (a given PDF/CDF, binomial, and a Beta posterior). Skip part (d): MLE of α.
  3. How Lucky! — geometric, Poisson approximation
  4. Probabilistic Supply Chains — joint distributions, marginals, conditional expectation (pseudocode)
  5. Chess.com Puzzles — Bayesian inference over a discrete unknown
  6. P-Hacking — counting, variance, the CLT, and p-values; an unusually good review of Lectures 15–16
  7. Calibration of ML Algorithms — part (b) is fair game (a binomial probability). Skip parts (a), (c), and (d): accuracy, calibration, and Platt scaling.

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


Old Final Exams

The old finals are the only place to find practice problems on the Multinomial, the Beta distribution, the Central Limit Theorem, bootstrapping and p-values, and information theory. They also contain problems on maximum likelihood estimation and machine learning, which are not on this exam — see the per-problem guide above for which problems to do and which to skip.

'