Midterm 1 — scope and plan
Tuesday 6 October, in class. What's on it, where each topic is taught here, and what to put on your one page of notes.
1. The rules, and what they imply
- One page, two sides.
- Hand-written — your handwriting only. No screenshots.
- You may handwrite it digitally and print it.
- You may collaborate on what goes on it, but the sheet must be yours.
Allowed and unnecessary, which tells you something: every number on the exam will be chosen to work out by hand. Entropies will land on halves, quarters, eighths and thirds. Matrices to invert will be 2×2 with clean determinants. If your arithmetic is getting ugly, you have probably made an error rather than hit a hard problem.
Practise the arithmetic, not just the method. Knowing that $I(Y;W) = H(Y) - H(Y\mid W)$ is worth nothing if you cannot evaluate $-\tfrac14\log_2\tfrac14 - \tfrac34\log_2\tfrac34$ without a calculator. The lookup table on the cheat sheet exists for exactly this, and copying a small version of it onto your notes page is probably the single highest-value use of that space.
2. Scope, mapped to this site
The staff listed four sources of exam material. Here is each one against what the site covers. Tick things off as you go — the boxes save in your browser.
| Topic | Taught here | Problems | |
|---|---|---|---|
| Search problems, state spaces, BFS / DFS / UCS | Ch 1 | P 1 · R 1 | |
| Heuristics, Greedy, A*, admissibility, consistency | Ch 2 | P 2 · R 1 | |
| Minimax, α-β pruning, expectimax, eval functions | Ch 3 | P 3 · R 2 | |
| CSPs, backtracking, forward checking, AC-3, MRV / LCV | Ch 4 | P 4 · R 2 | |
| ML formulation: loss, risk, empirical risk, ERM, i.i.d. | Ch 5 | P 5 | |
| Decision trees, stumps, majority vote, greedy splitting | Ch 6 | P 6 · R 3 | |
| Entropy, conditional entropy, mutual information | Ch 7 | P 6 · R 3 | |
| Linear regression, normal equations | Ch 8 | P 7 · R 5 | |
| Gradient descent, SGD, learning rate, gradients | Ch 9 | P 8 · R 4 | |
| Feature engineering, polynomial transforms, overfitting | Ch 10 | P 9 | |
| Logistic regression, sigmoid, cross-entropy, convexity, softmax | Ch 11 | P 9 · R 5 | |
| Model selection: regularization, hyperparameters, cross-validation | Ch 12 | P 9 · R 5 | |
| Problem formulation from scratch (Tower of Hanoi style) | Recitations | R 1 | |
| Ethics of deployed ML systems | Recitations | R 1 | |
| Vector derivatives and proofs | Ch 9 | R 4 |
3. What is not on it
The staff were explicit: material up to and including lecture 10, "i.e., no neural networks", and pre-reading excluding neural networks. The site has a neural networks chapter — it is not on this exam. Skip it entirely until after Tuesday.
That also means the chain-rule and computation-graph material in that chapter is out. But vector derivatives are still in, because they come from the optimization lecture and recitation 4, not from neural networks. Do not confuse the two.
Exam material includes homeworks 1–5, and this site does not cover them — the homework files were not available when it was built. Work those from your own submissions and the posted solutions. Everything else the staff listed is covered here.
4. Two days to learn, one to test
There are 58 problems across the recitations and the practice set, and roughly 122,000 words of chapters behind them. Reading the chapters front to back would take over twenty hours and is the lowest-yield thing you could do with two days. So don't.
Problems are the learning. Chapters are the lookup. Open a problem, attempt it on paper, and only when you get stuck or get it wrong do you open the chapter — and then only the section that failed you. Reading first feels productive and mostly isn't: it hides which things you can't actually do.
Day 1 — all of search, plus trees and entropy ~30 problems
| Do | Problems | Chapter to open only if stuck |
|---|---|---|
| Recitation 1 | 5 | Ch 1, Ch 2 |
| Recitation 2 | 7 | Ch 3, Ch 4 |
| Practice §1–4 | 12 | same four |
| Recitation 3 | 5 | Ch 6, Ch 7 |
Ends with Part I finished and the tree/entropy machinery started — which is the part of the ML half that behaves most like the search half, so it rides along well here.
Day 2 — the rest of machine learning ~28 problems
| Do | Problems | Chapter to open only if stuck |
|---|---|---|
| Practice §5–6 | 7 | Ch 5, Ch 6, Ch 7 |
| Recitation 4 | 5 | Ch 9 (vector derivatives) |
| Practice §7–8 | 6 | Ch 8, Ch 9 |
| Recitation 5 | 6 | Ch 11, Ch 12 |
| Practice §9 | 5 | Ch 10, Ch 11, Ch 12 |
Part II is about 40% larger than Part I and is more than half the exam, which is why it gets the cleaner, less interrupted day.
Day 3 — practice tests
The staff said practice questions would be posted in the resources section of Piazza. Day 3 is those, under timed conditions, with your notes sheet and no calculator — the same constraints as the exam. Then spend what's left re-working only what you got wrong, plus homeworks 1–5.
Write side A (search) at the end of day 1 and side B (ML) at the end of day 2, while the gaps you just hit are fresh. Deciding what earns the space is itself revision — it forces you to separate what you know from what you only recognise.
Then day 3's practice tests double as a test of the sheet. Every time you reach for something that isn't on it, that's a line to add. You cannot discover that on exam morning.
Cut the practice set before the recitations, and cut chapter problems before either. The recitations are the staff's own questions, so they are the best available signal about what the exam asks and how it asks it. Finishing recitations 1–5 and having a sheet you trust beats half-finishing everything.
5. What to put on the one page
You have two sides and your own handwriting. The temptation is to transcribe everything, which produces a sheet you cannot navigate under time pressure. Spend the space on two things: what you cannot re-derive quickly, and what saves arithmetic.
- $\log_2$ and binary-entropy tables — $\log_2 3 \approx 1.585$, $\log_2 5 \approx 2.322$, $\log_2 7 \approx 2.807$; $H(\tfrac12)=1$, $H(\tfrac13)\approx0.918$, $H(\tfrac14)\approx0.811$, $H(\tfrac15)\approx0.722$, $H(\tfrac25)\approx0.971$, $H(\tfrac38)\approx0.954$. No calculators, so this is pure speed.
- The A* conditions — admissible $0 \le h \le h^\star$ for tree search; consistent $h(n) \le c(n,n') + h(n')$ for graph search. Easy to state backwards under pressure.
- The α-β cutoff tests — in max-value,
if v ≥ β: return vthen $\alpha \leftarrow \max(\alpha,v)$; in min-value,if v ≤ α: return vthen $\beta \leftarrow \min(\beta,v)$. Getting the direction wrong costs the whole question. - Normal equations $\theta^\star = (X^\top X)^{-1}X^\top y$, and the scalar $w^\star = \frac{\sum x_i y_i}{\sum x_i^2}$.
- Gradient identities $\nabla(\theta^\top v) = v$, $\nabla(\theta^\top A\theta) = (A+A^\top)\theta$, and $\nabla\|y - X\theta\|^2 = -2X^\top y + 2X^\top X\theta$.
- Sigmoid facts $\sigma' = \sigma(1-\sigma)$, $\sigma(-z) = 1-\sigma(z)$, and the cross-entropy gradient $\frac1N\sum(\sigma(\theta^\top x^{(i)}) - y^{(i)})x^{(i)}$.
- AC-3's cost $O(n^2d^3)$ and the $d^n$ assignment count — pure recall, no derivation.
- The GD convergence condition for $J = cw^2$: $0 < \alpha < 1/c$.
- Full proofs. The A* optimality argument and the convexity proof are understanding, not lookup. If you need the proof written down you will not reconstruct it in the time available anyway.
- Definitions you can state in a sentence. Entropy, risk, ERM, a decision stump. Writing these out is how sheets fill up with things you already know.
- Worked examples. They eat enormous space and rarely match the exam's numbers.
- Pseudocode you understand. If you can run backtracking search by hand, you do not need its pseudocode; if you cannot, the pseudocode will not save you.
Group by when you'd reach for it, not by lecture. All the hand-arithmetic aids in one corner, all the "which condition applies to which search" material in another. Under time pressure you search your sheet by task, not by chapter number.
6. The traps, collected
These come from the cheat sheet's trap list and are the mistakes most likely to cost marks on this particular scope:
- Admissible is enough for A* tree search; graph search needs consistent. Why.
- In arc consistency you delete from the tail. Why.
- α-β preserves the value at the root, not necessarily at interior nodes. Why.
- A specific conditional entropy $H(Y\mid W=\omega)$ can exceed $H(Y)$ — only the weighted average cannot. Why.
- $x^{(i)}$ is a sample index, not an exponent.
- The minimax answer is an action, not just a value.
- Logistic regression is classification. The name is historical — it regresses the log-odds. Why.
- MRV wants to fail fast; LCV wants to succeed fast. The asymmetry is the whole idea, and it is easy to state backwards. Why.
- Exclude the bias term from the regularizer, and scale your features first. Why.
- UCS is A* with $h = 0$, which is why it is complete and optimal but explores in every direction.
Do recitations 1–5 — 28 problems, about four hours with a pen — and build your notes sheet. That is it. They are the staff's own problems, and deciding what goes on one page forces you to audit what you actually know.