AP CSP Day 56: Iteration Patterns | Cycle 2
Share
Loop invariants are conditions that remain true before, during, and after every iteration of a loop and can be used to prove a loop is correct. While the AP CSP exam does not require formal proof, understanding what a loop maintains across iterations helps students verify that an algorithm achieves its stated goal. Cycle 2 iteration review questions present loops with a stated intended behavior and ask students to determine whether the loop correctly implements it, or to identify the specific iteration where the result first diverges from the intended output. Tracing the first few and last few iterations is the most effective verification strategy.
📚 Study the Concept First (Optional) Click to expand ▼
Loop Correctness: Does the Loop Do What It Claims?
Intended vs. Actual Behavior
A loop that terminates without an infinite loop or off-by-one error may still produce the wrong result if its body logic is incorrect. A loop that accumulates a sum but accidentally multiplies instead will terminate correctly but produce a wrong answer on every input.
Verifying with Test Cases
The most reliable way to verify loop correctness is to trace it with a small, concrete input where you can compute the expected output manually. If the traced output matches the expected output, the loop is likely correct for similar inputs.
Practice Question
What is displayed after the following code runs?
x ← 1
total ← 0
REPEAT UNTIL x > 100
{
total ← total + x
x ← x * 2
}
DISPLAY(total)Trace: x=1,total=0. Iteration 1: total=1,x=2. Iteration 2: total=3,x=4. Iteration 3: total=7,x=8. Iteration 4: total=15,x=16. Iteration 5: total=31,x=32. Iteration 6: total=63,x=64. Iteration 7: total=127,x=128. Now x=128>100, loop stops. total=127.
A) 63 is total after 6 iterations, but x=64 is not > 100, so one more iteration occurs. C) 100 is the threshold, not the sum. B) 255 would require one additional iteration (x=256), but x=128 already exceeds 100.
Students stop one iteration too early (at total=63 when x=64) because 64 seems close to 100. The condition x > 100 is not met until x=128, so the iteration where x goes from 64 to 128 does execute.
REPEAT UNTIL checks the condition BEFORE each iteration. If the condition is still false (x ≤ 100), the loop body executes. Continue iterating until the condition is checked and found to be true.
Keep Practicing!
Consistent daily practice is the key to AP CSP success.
AP CSP Resources Get 1-on-1 Help