Invariants

Questions 1 to 5 of 6

1. 1. Put the steps of a loop proof in the order the lesson gives them.

   Use the arrows to put the steps in order.

   1. 1.Show that one pass keeps the invariant true before the next pass (the step)↑↓
   2. 2.At the stop, read the invariant to conclude the final answer (the end)↑↓
   3. 3.Check that the invariant holds before the first pass (the start)↑↓
   4. 4.Write the invariant as a plain statement about the variables before each pass↑↓
2. 2. In total = 0 followed by for i in range(len(marks)): with total += marks[i] in the body, which statement is the invariant before the pass with index i?

   total equals marks[i]total equals the total of marks[0..i-1]total equals the total of marks[0..i]total equals the largest value in marks[0..i-1]
3. 3. The running-maximum loop starts with best = 0 and then if scores[i] > best: best = scores[i]. Is the start best = 0 correct for [-5, -2, -9]?

   False, because the prefix before the first pass is empty and has no largest value, so best = 0 claims a value that is not in the list and the loop returns 0 instead of -2True, because 0 is smaller than every value in the list, so it never hides the real largest value
4. 4. Put these steps in the order to catch a broken running-sum invariant with an assert.

   Use the arrows to put the steps in order.

   1. 1.Add assert total == sum_of_prefix(values, i) as the first line of the loop body↑↓
   2. 2.Run it with python3 check_sum.py, where asserts are on by default↑↓
   3. 3.Read the AssertionError message to find the pass where the check failed↑↓
   4. 4.Write a helper sum_of_prefix(values, end) that adds the first end items with a plain loop↑↓
5. 5. The buggy running-sum loop has total = values[i] in place of total += values[i]. sum_of_prefix is the helper from the lesson. The file is run with python3 -O main.py, which turns asserts off, and values is [5, -2, 8, 3]. What does it print? ``python values = [5, -2, 8, 3] total = 0 for i in range(len(values)): assert total == sum_of_prefix(values, i), f"invariant broken at i={i}" total = values[i] print("sum =", total) ``

   sum = 14AssertionError: invariant broken at i=2sum = 3sum = 0