A First Taste of Algorithms · Problem Set 9

Concept & Counterexample

3.1 Claim: “you need calculus to know each operation’s blame-rule, so backprop can’t be elementary.” Half true. Show that each individual rule is a single Book 2 derivative (list the rules for +, ·, xⁿ, exp, log), and that the algorithm combining them needs no calculus at all — only graph traversal. State precisely where the mathematics lives and where the computer science does.

3.2 Claim: “a deeper network needs a more complicated backprop.” Refute using the chapter’s central structural fact: what does backward() actually operate on, and why is it blind to how deep or wide the network is? Construct the one-sentence argument that the same sixty lines train a 2-layer and a 200-layer network.

3.3 Claim: “the model generates real mathematician names, so it has memorized the list.” Distinguish, with the parrot exam: what would perfect memorization look like in the generated samples (and in the two loss curves)? What does the appearance of novel plausible names prove instead? Then the subtle case from the lab: if the model does emit some exact training names alongside novel ones, has it memorized? What single experiment settles it?

3.4 Claim: “softmax and cross-entropy are just two reasonable choices among many.” The deep water shows they are matched. Pair softmax instead with a different loss — squared error on the probabilities — and argue qualitatively why the gradient is messier and the learning signal less clean. (You need not compute it fully; identify what the clean “p − 1” structure depended on.)

3.5 Claim: “attention is fundamentally different from the simple model — a new kind of thing.” Argue the opposite from the chapter: name everything attention shares with the toy (the loss, the descent, the backward sweep, the softmax), and isolate the single thing it adds (learned, input-dependent weights over all prior positions). Is the transformer a new idea or a new arrangement of old ideas? Defend your answer.

3.6 Claim: “the √d_k scaling in attention is a minor numerical tweak.” Refute it with the mechanism: when query and key entries are independent with unit variance, what is the typical size of their dot product over d_k dimensions (think about summing d_k independent products — Chapter 7’s linearity of expectation, and what happens to the spread)? Then argue what an unscaled, large-magnitude score does to softmax (where do its outputs go?) and to the gradient through that softmax. The scaling is the difference between a head that learns and a head that is frozen at birth; say precisely why.

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