Questions: Loop Design and Invariants

Question 1

A loop maintains the invariant: 'At the top of each iteration, max_so_far holds the maximum of arr[0..i-1].' The loop runs from i=0 to i=n. What does the invariant tell us after the loop completes?

• A. Nothing — invariants are internal reasoning tools and make no guarantees about the final state
• B. That max_so_far equals the maximum of the entire array arr[0..n-1]
• C. That max_so_far equals arr[n-1], the last element examined
• D. That the loop ran without errors, but the correctness of max_so_far depends on the loop body

Answer: (B)

When the loop ends, i = n. Substituting into the invariant: max_so_far holds the maximum of arr[0..n-1] — the entire array. This is the 'termination' step of invariant reasoning: the invariant, combined with the loop's exit condition, directly gives you the postcondition you wanted. This is the power of invariants — they don't just describe what's happening inside the loop; they tell you what the loop achieves.

Question 2

A developer has a loop that passes most test cases but fails intermittently. What should they do first, according to loop invariant methodology?

• A. Add more print statements to trace variable values during execution
• B. Generate a larger random test suite to identify the failing input pattern
• C. Explicitly state the intended loop invariant and verify it holds at initialization, is maintained by each iteration, and implies the correct result at termination
• D. Rewrite the loop using a different algorithmic approach

Answer: (C)

Intermittent failures often indicate an invariant that holds for most inputs but breaks for edge cases — index 0, empty arrays, equal elements, etc. Writing down the invariant forces the developer to be precise about what the loop is supposed to maintain and immediately exposes which condition is actually failing. This approach finds the root cause rather than masking symptoms. Adding print statements (A) is debugging by inspection; explicitly reasoning about invariants is debugging by logic — it finds the problem faster and prevents similar bugs.

Question 3

A loop invariant must hold true before the very first iteration of the loop executes.

• T. True
• F. False

Answer: True

This is the 'initialization' requirement of loop invariant reasoning. The invariant must hold when execution first reaches the top of the loop, before any iterations run. For example, if the invariant is 'sum equals the sum of arr[0..i-1],' then before the first iteration (i=0), sum must equal the empty sum, which is 0. If the initialization step fails — e.g., sum was not set to 0 before the loop — the invariant never properly holds and the correctness proof breaks down immediately.

Question 4

A loop invariant is a condition whose variable values remain constant (unchanged) throughout nearly every iteration.

• T. True
• F. False

Answer: False

A loop invariant is a *relationship* that remains true, not a fixed value. The variables involved typically change each iteration — that is the point of the loop. The invariant for a summation loop is 'sum equals the sum of arr[0..i-1]': both sum and i change every iteration, but the relationship between them is always preserved. Confusing 'invariant' with 'constant value' is a fundamental misunderstanding. What is invariant is the truth of the statement, not the values of the variables.

Question 5

Explain how thinking about loop invariants can help you design a loop correctly in the first place, rather than just verifying a loop after writing it.

Model answer: Asking 'what should be true about my variables at the start of each iteration?' forces you to articulate the relationship the loop is supposed to maintain. That answer IS the invariant, and it dictates every decision in the loop body: what to compute, in what order, and how to update variables. For binary search, the invariant 'the target, if it exists, lies between indices low and high' tells you exactly how to pick the midpoint and which half to discard — every line has a clear justification. Without the invariant, these decisions are made by intuition and corrected by trial and error; with the invariant, off-by-one errors become visible before testing.

The key insight is that invariants are generative, not just verificational. A programmer who starts by asking 'what invariant do I want to maintain?' and then writes loop body code to maintain it will produce a correct loop. A programmer who writes code first and verifies afterward may produce a correct loop but cannot explain why each line is there — making future debugging and modification much harder.