Fill in the blanks Determine a Loop Invariant for the outer for loop of the Sele

Question

Fill in the blanks

Determine a Loop Invariant for the outer for loop of the Selection-Sort algorithm below that allows you to prove that the algorithm is correct. Then state the proof. Parts of both are given – fill in the blanks. Understanding how this algorithm works will give you the needed information to construct an appropriate loop invariant.

                 Selection-Sort (A: Array [1..n] of integer)

                 1               for i=n down to 2

                 2                                 position=i

                 3                                 for j=1 to (i–1)

                 4                                                   if A[j]>A[position] then position=j

                 5                                 if positioni then

                 6                                                   temp=A[i]

                 7                                                   A[i]=A[position]

                 8                                                   A[position]=temp

Explanatory Notes: The key here is to first understand how this algorithm sorts – by finding the position of the largest number in the array A[1,…n] and swapping that with the nth cell of the array, then finding the position of the largest number in the array A[1,…(n-1)] and swapping that with the (n-1)th cell of the array, and repeating this process for subarrays A[1,…(n-2)], A[1,…(n-3)],…,A[1,2]. Note that the outer loop is executed (n-1) times, with the value of the loop variable i going from n down to 2. So during the first execution of the outer loop (line 1), i=n, after which A[n] will contain the (first) largest number in the array and i will be decremented to n-1. During the second execution of the outer loop, i=n-1, after which A[n] will contain the first largest number in the array and A[n-1] will have the second largest number in the array and i will be decremented to n-2. During the third execution of the outer loop, i=n-2, after which A[n] will contain the first largest number in the array and A[n-1] will have the second largest number in the array, and A[n-2] will have the third largest number in the array and i will be decremented to n-3. During the kthexecution of the outer loop (we are using k to count the loop executions because the loop variable i is decremented and so does not count the number of executions of the loop itself), i=n-k+1, after which A[n] will contain the first largest number in the array and A[n-1] will have the second largest number in the array, etc., and i will be decremented to n-k.

Loop Invariant:

Before kth execution of the outer loop (line 1), the loop variable i=n-k+1, and ___________________ largest numbers in array A will be in the subarray _______________.

Initialization:

The LI should hold before the first execution of the loop: Before the 1st execution of the loop, the loop variable i=n-1+1=n, and 0th,…,1st largest numbers in array A will be in subarray A[(n+1)…n]. But both the 0thlargest number and the subarray A[n+1…n] are undefined for an array of n numbers. So the LI trivially holds.

Maintenance:

Here we have to show that if the LI held true before the kth execution of the loop, it must also be true after the kth execution, i.e., before the (k+1)th execution.

So suppose before the kth execution of the loop the LI holds, i.e., the loop variable i=n-k+1, and the ______________ largest numbers in array A are in the subarray _______________.

During this execution, the local variable position is initialized to i=n-k+1 (line 2).

The for loop executes for each value of j from 1 to (i-1)=(n-k) (line 3).

Each time, if a number A[j] greater than A[position] is found then position is updated to j. Therefore, since position starts out being (n-k+1) and j goes from 1 to (n-k), at the end of this loop, position will contain the index of the largest number in the subarray _______________.

Line 5 checks to see if this index is the same as i=(n-k+1). If it is, then nothing is done, and the largest number in subarray ___________ is in array cell __________. If it is not, then A[position] and A[n-k+1] are swapped by lines 6-8 so that the largest number in subarray ___________ is in array cell __________.

Since the ___________________largest numbers in array A were already in the subarray __________ before the kth execution of the loop started, this means that by the end of the kth execution of the loop, the kth largest number will be in array cell __________.

Finally, by the nature of the for loop, the loop variable i is decremented to n-k, and the kth execution of the loop finishes.

So after the kth execution of the loop finishes, i.e., before the (k+1)th execution of the loop, the loop variable i=______, and the ___________________ largest numbers in array A will be in the subarray ____________.

Thus, if the LI holds before the kth execution of the loop, it will hold before the (k+1)th execution of the loop.

Termination:

As we have proved initialization and maintenance, it holds that LI must be true after the loop finishes. The loop is executed (n-1) times. So after the (n-1)th execution, i.e., before the nth execution, the loop variable i=__________, and the _________________ largest numbers in array A will be in the subarray _____________. Since the first (n-1) largest numbers are thus now already sorted, what is in A[1] must be the nth largest, i.e., the smallest, number in the input array. Therefore A is fully sorted in the increasing order.

Explanation / Answer

oop Invariant
In computer science, you could prove it formally with a loop invariant, where you state that a desired property is maintained in your loop. Such a proof is broken down into the following parts:

Insertion Sort's Invariant
Say, you have some InsertionSort code, where the outer loop goes through the whole array :

Termination: Because the loop is a for loop, it clearly terminates.

Correctness: The loop exits when i = n. Thus, from the invariant, m is the maximum subsequence sum of A[0..n 1] when the loop terminates. Correctness case for Theorem 2.5 corrected 1/27/12. As can be seen from the above proof, initialization and maintenance can be shown using techniques we have already developed. Furthermore, the correctness step is simply logical inference. In the case of Theorem 2.5, termination is trivial, because for loops always terminate. Note, however, that in order for such a proof to be completed, it is essential that a proper loop invariant be chosen. Specifically, the invariant must be chosen so that: • it is true every time the loop condition is tested; • it is possible to prove that if it is true at the beginning of an arbitrary iteration, it must also be true at the end of that iteration; and • when coupled with the loop exit condition, it is strong enough to prove the desired correctness property. Thus, if we choose an invariant that is too strong, it may not be true each time the loop condition is tested. On the other hand, if we choose an invariant that is too weak, we may not be able to prove the correctness property. Furthermore, even if the invariant is true on each iteration and is strong enough to prove the correctness property, it may still be impossible to prove the maintenance step. We will discuss this issue in more detail shortly. CHAPTER 2. PROVING ALGORITHM CORRECTNESS 33 Figure 2.1 A loop whose termination for all n is unknown while n > 1 if n mod 2 = 0 n n/2 else n 3n + 1 For while loops, the proof of termination is usually nontrivial and in some cases quite difficult. An example that is not too difficult is IterativeInsert in Figure 1.6 (page 11). To prove termination of this loop, we need to show that each iteration makes progress toward satisfying the loop exit condition. The exit condition for this loop is that j 1 or A[j] A[j 1]. Usually, the way in which a loop will make progress toward meeting such a condition is that each iteration will decrease the difference between the two sides of an inequality. In this case, j is decreased by each iteration, and therefore becomes closer to 1. (The other inequality in the exit condition is not needed to prove termination — if it becomes true, the loop just terminates that much sooner.) We can therefore prove the following theorem. Theorem 2.6 The while loop in IterativeInsert always terminates. Proof: We first observe that each iteration of the while loop decreases j by 1. Thus, if the loop continues to iterate, eventually j 1, and the loop then terminates. Proving termination of a while loop can be much more difficult than the proof of the above theorem. For example, consider the while loop shown in Figure 2.1. The mod operation, when applied to positive integers, gives the remainder obtained when an integer division is performed; thus, the if statement tests whether n is even. Though many people have studied this computation over a number of years, as of this writing, it is unknown whether this loop terminates for all initial integer values of n. This question is known as the Collatz problem. On the other hand, when algorithms are designed using the top-down approach, proving termination of any resulting while loops becomes much CHAPTER 2. PROVING ALGORITHM CORRECTNESS 34 easier. Even if an examination of the while loop condition does not help us to find a proof, we should be able to derive a proof from the reduction we used to solve the problem. Specifically, a loop results from the reduction of larger instances of a problem to smaller instances of the same problem, where the size of the instance is a natural number. We should therefore be able to prove that the expression denoting the size of the instance is a natural number that is decreased by every iteration. Termination will then

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.