A First Taste of Algorithms

Problem Set 9

✦ ✦ ✦

Lab 9 (The Engine) is the Computational Lab tier — the chapter’s claims are not real until the engine trains in your hands. The Diamond’s derivation is checked against your own engine’s output.

Fluency

1.1 By hand, build the Value graph for L = (a + b)·c with a = 2, b = 3, c = 4: draw each node, its value, and its parents. Then run backprop on paper — seed the output with grad 1, apply each operation’s blame-rule — and find ∂L/∂a, ∂L/∂b, ∂L/∂c. (Check: ∂L/∂c should be a + b = 5.)

1.2 For the addition rule, explain in one sentence why blame passes to both parents unchanged; for the multiplication rule, why blame is scaled by the other factor. Tie each to a derivative from Book 2.

1.3 Trace the backward method’s depth-first build on the graph of 1.1: in what order are the nodes appended, and why must the output node be processed first in the reversed walk? Connect to Chapter 5’s claim that this traversal is Chapter 3’s recursion.

1.4 A single neuron with two inputs has how many knobs? A layer of 4 such neurons? A two-layer network, 2 inputs → 4 hidden → 1 output? (Count weights and biases separately, then total — this is the skill Lab 9 uses to size the real model.)

1.5 Softmax by hand: scores [1, 2, 0] → probabilities (use e¹, e², e⁰; normalize). Then compute the cross-entropy loss if the true class is the middle one, and—using the deep water’s formula—the gradient on all three scores. Confirm they sum to zero, and say in one sentence why they must.

1.6 “The model feeds its own output back as input to generate.” Walk through generating a 4-letter name by hand given a model that always predicts the most likely next letter from a tiny table you invent — show the context sliding forward one letter at a time, including the start and stop markers.

Practice

2.1 Extend the Value class with a subtraction rule (__sub__) and state its blame-rule, deriving it from addition and negation. Then a division rule — harder; use a·b⁻¹ and the power rule, and write the blame-rule for b⁻¹ explicitly. (Lab 9 has you test both against finite differences.)

2.2 A model’s training loss after each epoch: 3.1, 1.9, 1.3, 1.1, 1.05, 1.02. Its held-out loss: 3.0, 2.0, 1.8, 2.1, 2.6, 3.2. Plot both by hand (rough axes), mark the epoch where you would stop training, and explain in the chapter’s language what is happening to the model after that point. What is it learning instead of the pattern?

2.3 Temperature in generation: sampling divides scores by a temperature T before softmax. Predict, with reasoning, what the generated names look like as T → 0 (very small) and as T → large. (Lab 9 measures both; commit to predictions first.) Connect T to a knob you have already met — what does dividing all scores by a constant do to their softmax spread?

2.4 Attention as weighted looking-back: a model guessing the letter after “albe—” has learned attention weights over the five prior letters. Invent plausible weights (summing to 1) that would help predict “r”, and explain which letters earn the weight and why. Then change the stem to “albea—” and argue how the weights should shift. (You are reasoning about what the figure’s arcs encode.)

2.5 Parameter counting at scale: your name model has ~Q knobs (use your 1.4 method on Lab 9’s actual dimensions — you should land near eight thousand). A frontier model has ~10¹². Compute the ratio as a power of ten, and then a humbling comparison: if your knobs were seconds, how long is your model’s training; if theirs were seconds, how long is theirs? (The gap between “an afternoon” and “an age” is the gap the last deep water is about.)

2.6 Query, key, value by hand. A single attention head has d = 4, and at some position the query is q = (1, 0, 1, 0). Three earlier positions have keys k₁ = (1, 0, 0, 0), k₂ = (1, 0, 1, 0), k₃ = (0, 1, 0, 0). Compute the three dot products q·kₛ, divide by √d, and apply softmax to get the attention weights. Which position does this query attend to most, and why does the direction of the key vectors — not their labels — decide it?

2.7 The mask, concretely. Write the 4×4 matrix of raw scores for a length-4 sequence as a general grid, then show exactly which entries the causal mask sets to −∞ and what the matrix looks like after. After softmax, why is the resulting attention matrix lower-triangular, and what would a model that skipped the mask be able to do that makes its low training loss worthless? (Lab 9 Break-it 5 is this problem, executed.)

2.8 Dimensions audit. For the lab’s head (d = 32, d_k = 32, vocabulary V, sequence length T), give the shape of every matrix in the five equations: X, Q, K, V, QKᵀ, A, the context AV, and the logits. Confirm the chain of shapes is consistent (each product’s inner dimensions match), and identify which single matrix’s row-count is “one per possible character” rather than “one per position.” (This shape-checking is most of what catches bugs in real model code.)

All 32 chapters of A First Taste of Algorithms · Foundations · All courses