A First Taste of Algorithms

Problem Set 8

✦ ✦ ✦

Lab 8 (Downhill) is the Computational Lab tier; problems 2.4, 3.3, and the Diamond’s part (d) use its runs as evidence.

Fluency

1.1 Run gradient descent by hand on f(x) = x², f′(x) = 2x, with η = 0.1 from x₀ = 5, for four steps, keeping three decimals. What constant factor multiplies x each step? Check it against 1 − 2η.

1.2 For the loss L(w) = average of (w·xᵢ − yᵢ)² on the two examples (1, 2) and (2, 5): compute L(0), L(2), and L(3) by hand. Which of the three candidate slopes is best, and what is each prediction actually missing by?

1.3 Differentiate the one-example loss ℓ(w) = (w·x − y)² with respect to w (Book 2’s chain rule, one application). Then state the descent update for w in terms of the miss (w·x − y) — and read it aloud as a sentence about blame: which examples move the knob hardest, and in which direction?

1.4 Nearest neighbor by hand: examples at (1, 1) PASS, (2, 4) PASS, (4, 1) FAIL, (5, 4) FAIL. Classify the points (3, 1), (3, 4), and (3, 2.5) — distances computed explicitly (squared distances suffice; why may you skip the square root when only comparing?). One of the three is a genuine coin flip; which?

1.5 On the two-valley landscape f(x) = x⁴ − 3x² + x, evaluate f and f′ at x = −0.5 and x = +0.5, and state — from the signs alone, before any descent — which direction each walker’s first step takes and which valley therefore claims it.

1.6 The stride taxonomy: for η = 0.05, 0.4, 0.5, 0.75, 1.0, 1.2 on the bowl, compute the factor 1 − 2η and classify each stride’s fate in one word (crawl / converge / one-step / ring-inward / ring-forever / explode).

Practice

2.1 Hours studied x, test score y, three students: (2, 65), (4, 72), (6, 91). Fit y ≈ w·x by hand-cranked descent: start w = 0, η = 0.01, run four steps with the gradient from 1.3 (calculator encouraged, three decimals). Then sanity-check your w against the crude estimate “average of y/x.” Is descent heading there?

2.2 A delivery company predicts delivery time as w · (distance). Their loss is squared misses. A rival argues for absolute misses, |w·x − y|, because “a 20-minute miss is exactly twice as bad as a 10-minute miss, not four times.” Both positions are defensible — give one realistic scenario favoring each loss, then state which one this chapter’s machinery prefers and point to the exact sentence of the descent method that explains why (what does the update need to exist at every point?).

2.3 Nearest neighbor for music: each song is a point (loudness, tempo), labeled “morning” or “night” by a user’s history. Design six example songs (your numbers) such that one plausible new song gets a label you’d call wrong despite the algorithm working perfectly. What feature is missing from your points, and what does this say about where a learner’s competence actually lives — the algorithm, or the representation?

2.4 The several-starts gamble. On the two-valley landscape, suppose starting points are drawn uniformly from [−2, 2], and (from your lab runs or 1.5’s reasoning) starts below the hilltop at ≈ 0.17 reach the deep valley. What is the probability one random start finds the deep floor? How many independent starts before the probability of missing it drops below 1%? (Chapter 7’s machinery: the misses must all happen together.) State the general trade this strategy makes, in the currency-language of this book.

2.5 The parrot exam: a learner is graded 98% on its training examples and 71% on held-out examples. A second learner scores 84% and 82%. Which would you deploy, and what single number — define it — summarizes why? Then construct the cautionary scenario: describe circumstances under which even the honest test score misleads (think: where did the test examples come from, and where will tomorrow’s questions come from?).

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