Invariants

Questions 1 to 5 of 6

1. 1. Put the three checks for a loop invariant in the order you do them.

   Use the arrows to put the steps in order.

   1. 1.Keep: a pass that starts with a true statement leaves it true↑↓
   2. 2.Start: the statement is true before the first pass↑↓
   3. 3.End: when the loop stops, the statement and the failed test give the answer↑↓
2. 2. Put these steps in order when you write a maximum loop from its invariant.

   Use the arrows to put the steps in order.

   1. 1.Choose a start that makes the invariant true before the first pass: best = values[0], after an empty check↑↓
   2. 2.Write the body so that best changes only when a new value is larger↑↓
   3. 3.After the loop, read the invariant as the answer: best is the largest value in the list↑↓
   4. 4.State the invariant: best is one of the values seen, and it is at least as large as each of them↑↓
3. 3. Example 2 in the lesson sets best = 0 and then loops over the values -4, -7, -12 and -3. What does the program print?

   -3, the largest value in the list-12, the smallest value in the list0, a value that is not in the listThe program crashes with an out-of-range error
4. 4. In the invariant proof, which of the three parts does the most work?

   Start: the statement is true before the first passEnd: the statement is true after the loop stopsDeclare: the variables get their typesKeep: a pass that starts with a true statement leaves it true
5. 5. True or false: an assert on the invariant, placed inside the loop, proves the invariant for every possible input once the program runs without stopping.

   True, because the assert checked every pass that ranFalse, because the assert only checked the inputs this run used