Unit 5.8 · about 3 h
126 / 324Recurrence proofs and differential validation
Samples pass and proofs fail. A differential harness plus a minimized counterexample is what catches a wrong recurrence.
- derive
- measure
You can now
- Prove a recurrence by induction with the invariant, exchange step or cut property stated, not restated.
- Build a Hypothesis harness that compares memoized, tabulated and brute-force results on small inputs.
- Shrink a failure to a minimal counterexample and map it to the violated claim.
Covers
- Inductive recurrence proofs and loop invariants
- Exhaustive small-instance and differential validation
Study, in this order
4 steps
- The proof checklist and a model argumentAlgorithms - dynamic programming
Section 3.4 (pp. 105-107), the step checklist that ends "you have to prove that each of these steps is correct"; Section 3.7 Recursive Structure (pp. 111-112) as the model optimal-substructure argument
- First property test with pytestHypothesis - exhaustive and differential DP tests
Write your first test and Combining Hypothesis with pytest
- Strategies for small instancesHypothesis - exhaustive and differential DP tests
Strategies Reference: Numeric (integers) and Collections (lists) for generating small valid instances
- Replaying shrunken failuresHypothesis - exhaustive and differential DP tests
The Hypothesis database; Using
@exampleto run a specific input; Prefer@exampleover the database for correctness
Focus on
- A proof names the invariant and the step: last-column cases for edit distance, shorter-interval reads for OBST, both worlds for tree tuples.
- The harness generates small valid inputs, runs three implementations, and keeps the shrunk failure. Brute force is the oracle, not a fourth opinion.
- Derandomize the settings for the reproduce run so the example count and seed replay exactly.
Reproduce closed-book
In Python 3.13 with Hypothesis 6.169 and pytest:
@given lists of ints 0-9 with length at most 8, max_examples = 200, derandomize = True. Compare memoized, tabulated and brute-force House Robber on every example: all 200 pass. Then plant the alternating-parity variant: Hypothesis shrinks the failure to [1,0,0,1] with parity 1 versus optimal 2.Traps
- Testing only on statement samples. The parity variant passes both LC 198 examples (
[1,2,3,1]and[2,7,9,3,1]) and fails first on[1,0,0,1]; generate, do not hand-pick. - Comparing two optimized forms with no brute-force oracle. Agreement proves consistency, not correctness; the exhaustive baseline is the check.
- Generating invalid instances such as negative coins or empty grids. Constrain generation to valid inputs or failures indict the generator, not the recurrence.
Practice
The section mini-project covers this: a Hypothesis differential harness over memoized, tabulated and brute-force forms with retained shrunk failures and one repaired recurrence.
Self-test
-
What does the edit-distance contradiction actually establish?
That removing the last column of an optimal alignment leaves an optimal alignment of the prefixes. With the three possible last-column shapes, the three-way min considers every optimum, and each option it considers is a valid alignment. -
Why three implementations instead of two?
Memoized and tabulated share the recurrence, so a wrong recurrence passes their comparison. Brute force derives from the definition, so it disagrees exactly when the recurrence is wrong. -
Hypothesis shrinks a failure to
[1,0,0,1]. What do you do?Pin it with@example([1, 0, 0, 1])so it runs on every test run, then map it to the claim: the alternating pick returns 1, while taking both ends and skipping the middle returns 2, which indicts the parity assumption. -
A proof says by optimal substructure, the recurrence holds. What is missing?
The argument itself: which cases exhaust the optimum, why the tail is optimal for the subproblem, and why no invalid solution is admitted.
Completion criterion
Stop when
Your harness passes 200 derandomized examples on the correct code and exhibits a minimized counterexample on the planted bug.
Mark passed, then open 5.9 Only mark this when you can do it without notes.Leads to
- 5.9 Dynamic programming as shortest paths, formulations and limits Carry proof and counterexample habits to transfer problems.
- 3.6 Dijkstra, Bellman-Ford and negative cycles Prove relaxation invariants with the same induction shape.
Comes after
- 3.8 Graph certificates and exhaustive small-graph validationApply the same oracle discipline to recurrences: brute force on small instances first.
- 4.6 Reservoir sampling, unbiased shuffling and empirical checksCarry property and differential testing into recurrence validation.
- 5.4 Sequence and string dynamic programmingProve the string recurrences and validate them against brute force.
- 5.6 Tree dynamic programmingProve the per-node recurrence and test it against brute force.
- 5.7 Knapsack, subset and bitmask dynamic programmingValidate loop directions with differential tests that catch reuse bugs.
Resources for this unit
- Algorithms - dynamic programming Use the dynamic-programming chapter to derive states and recurrences from first principles and to separate DP from greedy reasoning and shortest paths.
- Hypothesis - exhaustive and differential DP tests Generate small valid instances, compare memoized, tabulated and exhaustive results, and retain shrunk failures for wrong state, base case, order and compression defects.
Also in this section
- DSA Handbook - dynamic programming Study Part 9 in order from state and recurrence through sequence, grid, tree and bitmask families. For every example, close the page and reconstruct the state, transition and evaluation order.
- AlgoMaster DSA - dynamic programming slice Attempt Coin Change, Longest Common Subsequence and House Robber III cold. Write the state, transition, base case and evaluation order first; compare against brute force on small inputs and reconstruct a witness when available.
- NeetCode - unseen mixed problems Use two tag-hidden mixed problems as the final transfer test. One must require rejecting a tempting greedy or insufficient-state solution with a counterexample.
- Python sys: recursion limit Read
sys.getrecursionlimitandsys.setrecursionlimit: the limit guards the C stack and its safe maximum is platform-dependent. Check the default withgetrecursionlimit(1000 on CPython 3.13), raise it once for memoized DP, or switch to tabulation for deep inputs. - Erickson lecture note D - Advanced Dynamic Programming Read Section D.1 (Saving Space: Divide and Conquer) for the Hirschberg Half-table split that recovers an optimal edit sequence in \(O(m + n)\) space.
- Erickson lecture note J - Approximation Algorithms Read Section J.1 (Load Balancing) for the Partition reduction that makes exact scheduling NP-hard, the
GreedyLoadBalanceheuristic, and Theorem J.1 with its factor-2 proof.