Proving a loop right on every input

Computing · Algorithms & Data Structures · ages 18-19

Name ______________________ Date ____________

To call a loop correct, what must be true?
- It gives the right answer for every allowed input and it stops
- It runs fast on the inputs you tried
- It works on whole numbers at least once
Which three checks make a statement a loop invariant?
- True before the loop, true after one pass, true after two passes
- True before the loop, kept true after every pass, giving the goal at the end
- True when the loop stops, true when it crashes, true when it hangs
You tested your loop on fifty inputs and all passed. Why is it still not proven right?
- Fifty tests are too few for any conclusion at all
- One more untried input always waits and might break it
- Testing can only check spelling, never behavior
A loop runs like this: start with x = 5. While x is not 0, print x, then subtract 1 from x. To call this loop correct, what must be true?
- It prints 5, 4, 3, 2, 1 and then stops
- It prints as long as the computer is on
- It prints the numbers forever without stopping
- It only needs to work when x starts at 5
A loop starts with x at 5, prints x, subtracts 1, and repeats while x is not 0. What happens?
- It prints 5, 4, 3, 2, 1 and then stops
- It prints forever without ever stopping
- It prints nothing because 5 is not 0
The loop that halves its number while it is even ends for every possible starting value.
Circle one: True False
A friend claims this loop always ends: while n is even, replace n with n divided by 2. Which starting value makes the loop run forever?
- n = 16
- n = 0
- n = 7
- n = 12
A loop adds up a list of any length. Which statement works as its invariant?
- The total grows by exactly one on every pass
- The total always equals the sum of the whole list
- The total equals the sum of the items seen so far
A friend claims the total always equals the full sum as the invariant of a summing loop. Which observation breaks this claim?
- Some inputs loop forever, like 0 in the halving loop
- A one-item list finishes in a single pass
- A list checked halfway, where unseen items are missing from the total
An insertion sort loop ends after handling every card. Its invariant says the handled cards sit in order. What follows?
- Only the earliest card is sorted and the rest are unknown
- The whole array is sorted because every card was handled
- The loop must run again to confirm the order

Answer key

For grown-ups. Fold this page away before handing over the rest.

Proving a loop right on every input W1-mt_fWnstju2ns-s1

It gives the right answer for every allowed input and it stops · Correctness is the right answer on all inputs plus a guaranteed stop.
True before the loop, kept true after every pass, giving the goal at the end · Entry, every pass, exit: miss one and the proof falls apart.
One more untried input always waits and might break it · Testing finds mistakes but cannot cover every input you never tried.
It prints 5, 4, 3, 2, 1 and then stops · A correct loop must do two things: produce the right output and actually stop. Tracing the values of x shows it prints 5 lines and ends.
It prints 5, 4, 3, 2, 1 and then stops · Trace x downward: after printing 1, x reaches 0 and the loop ends.
False · Zero breaks it: 0 is even and half of 0 is 0 forever.
n = 0 · The input n = 0 breaks the claim. Zero is even, and half of zero is still zero, so the loop never escapes.
The total equals the sum of the items seen so far · Partway through, only the seen items can be counted in.
A list checked halfway, where unseen items are missing from the total · Halfway through, the total cannot yet equal the full sum. Repair it to the sum seen so far.
The whole array is sorted because every card was handled · At exit the handled part is the whole array, so ordered handled cards mean a sorted array.