Problem Solving: Worked Examples
Work through each trace before reading the explanation. Then solve the transfer task without the page open.
Example 1: A counterexample changes the strategy
For coins 1,3,4 and amount 6, greedy chooses 4+1+1. The optimum is 3+3. The local choice lacks a proof that it preserves an optimal completion.
Define best[a] as the fewest coins for amount a, with best[0]=0. Try each possible final coin and reuse smaller solutions. Values for amounts 0 through 6 are 0,1,2,1,1,2,2. A reusable subproblem handles the counterexample without a special-case patch.
Example 2: Minimize the failure predicate
A sum function skips the last array entry. A 1000-element failure can shrink to [7]: expected 7, observed 0. An empty array is smaller but no longer fails.
Minimization preserves the property “actual sum differs from expected sum.” It does not blindly remove all data. The minimal case exposes the loop-boundary assumption and becomes a useful regression test.
Transfer and self-check
Find a greedy counterexample for coins 1,5,6. Check: amount 10 gives five greedy coins versus two coins of value 5.
Evidence to keep
Save your first attempt, corrected reasoning, and transfer result as checkpoint evidence. A matching final answer without an explanation is insufficient. Continue with the guided lab and use the reading guide to repair a specific gap.
Example 3: A search boundary survives an empty interval
Find the first value at least 3 in [1,3,3,7]. The lower-bound loop starts with (lo,hi)=(0,4). Midpoint 2 has value 3, so hi becomes 2; midpoint 1 has value 3, so hi becomes 1; midpoint 0 has value 1, so lo becomes 1. Return 1. The final half-open interval [1,1) contains no elements. The invariant concerns the two excluded partitions and a boundary in the closed interval [lo,hi], not an existing target index inside the half-open interval.
For target 9 the boundary is 4, which is a valid insertion position but not an
array index. Membership therefore checks p < len(a) before a[p] == target.
The loop variant hi-lo proves termination independently of the partition proof.
Transfer: replace >= with > in the contract. On duplicates, the answer must move past all equal keys. Name the changed comparison and revise the invariant.
Example 4: A smaller failure need not be a global minimum
Let a deterministic predicate fail exactly for lists of length 1 or 3. Starting from [4,5,6], every single deletion gives length 2 and passes. A single-deletion reducer correctly stops: the input is 1-minimal. Yet [4] also fails and is shorter. This does not contradict the reducer's contract; it disproves a stronger claim that the contract never made. The reduction relation is part of the evidence.
For a function that skips the final sum element, failure means the last value is nonzero. Shrinking [0,7,0,2] can produce [2]; removing 2 gives an empty list where both expected and actual sums are zero. Save [2] as a regression case, then test a fresh negative singleton to avoid repairing only that literal input.