A First Taste of Algorithms · Problem Set 8

Diamond

4.1 The first convergence proof. Gradient descent on f(x) = x², update x_{k+1} = x_k − η·2x_k. (a) Show x_{k+1} = (1 − 2η)·x_k exactly, and unroll: x_k = (1 − 2η)ᵏ·x₀. (b) Prove: if 0 < η < 1 then |1 − 2η| < 1 and x_k → 0 — convergence, geometric, from every starting point. (Where in this argument does Chapter 7’s “geometric series ruled by its ratio” — Chapter 3’s, originally — make its return?) (c) Classify the boundary and beyond: η = 0.5, η = 1, η > 1 — state each fate and prove it from the unrolled formula. (d) Reconcile with your lab: match each η you ran to its predicted fate, and identify the run whose loss curve “rang.” What sign pattern in x_k is the ringing? (e) The honest perimeter: every step above leaned on f′(x) = 2x being exactly linear. Point to the precise line of (a) that fails for a general bowl like f(x) = x² + x⁴ — then state, without proof, which conclusion you’d still bet on and which (the magic of η = 0.5) you’d abandon. Knowing what survives generalization is the skill this part grades.

Computational Lab

5.1 Lab 8 in full, predictions before runs. Export three artifacts for the problem set: your η-fate table (Diamond d), your two-valley endpoints (2.4), and your train/test gap before and after the poisoned label (3.3).

Teach It

6.1 Blindfold someone (or have them close their eyes) on a gentle slope — a yard, a wheelchair ramp, a hallway with a tilted board — and ask them to find the lowest point using only the feeling under their feet, narrating their rule aloud. Then tell them that’s the algorithm training every AI they’ve heard of, and let them object. Their best objection is the chapter’s content; write down which one they found (valleys? stride size? “what if the ground is flat”?) and how far they got unprompted.

6.2 Explain the parrot exam to a younger student using actual flashcards: train them on ten cards, test on the same ten, then on five new ones, and discuss the two scores. Then the reveal: every AI benchmark they’ve seen a headline about is the five new cards — and the entire trustworthiness of the field hangs on those cards being genuinely new. Report their reaction, and your own honest answer to the question they will ask: “how does anyone know the test cards weren’t in the training pile?” (Welcome to a real and current controversy.)

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