Loops and invariants
1.[2p] How many times does the body of for (let i = 3; i < 12; i += 2) run?
How many times does the body of for (let i = 3; i < 12; i += 2) run?
2.[3p] What is a loop invariant?
What is a loop invariant?
The answer is: A claim about the state that holds before the loop, is preserved by every pass, and is strong enough at the end to give the wanted result
The answer is: A claim about the state that holds before the loop, is preserved by every pass, and is strong enough at the end to give the wanted result
The answer is: A claim about the state that holds before the loop, is preserved by every pass, and is strong enough at the end to give the wanted result
3.[2p] Put the three parts of a loop in the order the machine reaches them for the first time.
Put the three parts of a loop in the order the machine reaches them for the first time.
The update
The initialisation
The condition
Show the answer
c, a, b
4.[3p] for (let x = 0; x < 1; x += 0.1) steps++; How many times does the body run?
for (let x = 0; x < 1; x += 0.1) steps++; How many times does the body run?
5.[2p] The Collatz loop has been checked by computer for every starting value below about without exception, which counts as a proof that it always terminates.
The Collatz loop has been checked by computer for every starting value below about without exception, which counts as a proof that it always terminates.
The answer is: False
6.[3p] Which of these are reasons for the for (let i = 0; i < n; i++) convention?
Which of these are reasons for the for (let i = 0; i < n; i++) convention?
Select all that apply
The answer is: The number of passes is n, readable off the header with no arithmetic, Two adjacent half open ranges join with no gap and no overlap, It matches array indices, where the first element is at 0 and the last at n - 1
7.[2p] How many trial divisions does for (let d = 2; d * d <= n; d++) perform for n = 97?
How many trial divisions does for (let d = 2; d * d <= n; d++) perform for n = 97?
8.[3p] Match each term to what it means.
Match each term to what it means.
Invariant
Variant
Accumulator
Fencepost error
Infinite loop
a name declared outside the loop and updated inside it
a claim the body preserves on every pass
counting the gaps when you meant the boundaries
a whole number that strictly decreases and cannot go below zero
a condition that never becomes false because the state stops changing
Show the answer
Invariant: a claim the body preserves on every pass Variant: a whole number that strictly decreases and cannot go below zero Accumulator: a name declared outside the loop and updated inside it Fencepost error: counting the gaps when you meant the boundaries Infinite loop: a condition that never becomes false because the state stops changing
9.[2p] A program neither crashes nor prints anything and never returns. What is the most likely cause?
A program neither crashes nor prints anything and never returns. What is the most likely cause?
The answer is: A loop whose state is not being changed, so its condition never becomes false
The answer is: A loop whose state is not being changed, so its condition never becomes false
The answer is: A loop whose state is not being changed, so its condition never becomes false