Objectives#
- State preconditions and postconditions that make the problem contract testable.
- Use a loop invariant and termination argument to justify an iterative algorithm.
- Use induction intuition to connect a smaller solved state to the next state.
- Challenge greedy rules with small counterexamples and justify DP state and transitions when local choice is unsafe.
Bound the claim with a contract#
A precondition describes valid input: for example, indices satisfy 0 ≤ left ≤ right ≤ n. A postcondition describes the promised result: the returned value equals the sum of input[left:right], and the input is unchanged. Invalid-input behavior belongs to the contract rather than being invented halfway through implementation.
Check the reasoning
- Which assumptions come from the prompt, and which must be clarified?
- Can a test determine whether the postcondition holds?
Preserve a truth about the processed prefix#
For a running prefix sum, before processing input[i], total equals the sum of input[0:i]. Adding input[i] makes total equal the sum of input[0:i+1], so the invariant is restored for the next iteration. It starts true because the empty prefix sums to zero.
Correct partial progress is not enough: the algorithm must terminate. Here i increases by one and is bounded above by n. When the loop ends at i=n, the invariant yields the required full-array sum.
Check the reasoning
- Why is the invariant true before the first iteration?
- Why does one iteration preserve it, and what does it imply when the loop terminates?
Use the smallest useful counterexample#
A counterexample must satisfy the input contract and make the claimed rule return a wrong result. Small examples are best because the decisive choice is visible. Try ties, boundaries, one repeated choice, and a case where a locally attractive decision blocks a better combination.
Check the reasoning
- Does the example refute the rule rather than a coding typo?
- Can you shrink it while preserving the failure?
Separate a greedy rule from a proved safe choice#
A greedy algorithm commits to a local choice. It needs an argument - often an exchange argument or a staying-ahead invariant - that an optimal solution can include that choice. A few successful examples do not supply the proof.
Dynamic programming is appropriate when overlapping states and an optimal-substructure recurrence capture choices that cannot safely be committed early. Define what dp[x] means before writing transitions, include reachable base states, and evaluate dependencies in a valid order.
Check the reasoning
- What property makes the greedy choice safe for every remaining subproblem?
- If using DP, what exact question does one state answer and which smaller states justify each transition?
Worked example: Reject an unjustified largest-coin rule#
Make amount 6 with unlimited coins of denominations 1, 3, and 4 while minimizing the number of coins. Test the rule “always take the largest coin that fits.”
| Step | State | Why it matters |
|---|---|---|
| Greedy choice | remaining 6 → take 4 → remaining 2 | Four is the largest denomination that fits, so the rule commits to it. |
| Greedy completion | 4 + 1 + 1 = 6; 3 coins | Only ones fit after the first choice, yielding three coins. |
| Counterexample | 3 + 3 = 6; 2 coins | A valid solution uses fewer coins, so the greedy rule is not correct for this denomination system. |
| DP state | dp[x] = minimum coins needed to make exactly x | The state keeps alternatives open instead of assuming the first coin is safe. |
| Transition at 6 | dp[6] = 1 + min(dp[5], dp[3], dp[2]) = 2 | Choosing coin 3 after an optimal amount 3 produces the two-coin result. |
Conclusion: The counterexample disproves the general greedy claim. Dynamic programming is justified by a precise state and recurrence, not merely by the presence of choices.
Misconception to correct#
If a greedy rule works on several examples and uses the best-looking local choice, it is correct.
Examples can reveal a failure but cannot prove the rule for every valid input. Supply a safety argument, or keep competing choices in a state model such as DP.
Short exercise#
Prove that a loop computing total += input[i] returns the sum of an n-element array. State the invariant, initialization, maintenance, termination, and one relevant precondition.
Reveal the worked answer
Invariant: before iteration i, total equals the sum of the half-open prefix input[0:i]. Initialization: at i=0 the prefix is empty and total=0. Maintenance: adding input[i] makes total the sum of input[0:i+1]. Termination: i increases by one until n, so the invariant gives the sum of input[0:n]. A relevant precondition is that addition and the accumulator representation can express the required result under the stated numeric model.
Put it into practice#
Choose a prefix-sum problem. Write the state meaning, initialization, preservation step, termination condition, and one counterexample to a tempting boundary convention before coding.
Practice an invariant before implementation