Let A and B be two one-dimensional arrays of length n of some value type. The fo

Question

Let A and B be two one-dimensional arrays of length n of some value type. The following algorithm implements an operation that swaps each of the elements of A with the corresponding element of B. for i 0 to n 1 do t B[i] B[i] A[i] A[i] t Give an invariant for the swap operation that captures the work done. Do not use e.g. true as your invariant. Show that your invariant is indeed an invariant.

. (30 points) Invariants Let A and B be two one-dimensional arrays of length n of some value type. The following al gorithm implements an operation that swaps each of the elements of A with the corresponding element of B. tor i 0 to n _ 1 do Give an invariant for the swap operation that captures the work done. Do not use e.g. true as your invariant. Show that your invariant is indeed an invariant.

Explanation / Answer

Invariants are basically used to check that the algorithm being used is correct or not, that is whether it is performing the required operation(here, swapping of elements) or not, In the given case we will use a loop invariant to check the correctness of the swapping algorithm. A loop invariant should satisfy the following three properties -

1. Initialization-  The loop invariant is true for the first iteration of the loop

2. Maintenance- If the loop invariant is true before an iteration of the loop then it also remains true for the next iteration.

3. Termination-  The termination of the loop gives us a property that shows the correctness of the algorithm.

In our case we'll be using the subarrays A[0....i-1] and B[0....i-1] as the loop invariants.

Step 1- Initialization :-

For the first iteration of the loop, we have A[0] and B[0] as the loop invariants. These are nothing but single elements that get swapped after the first iteration is completed. Thus the loop invariant is true for the first iteration o the loop,

Step 2- Maintenance :-

For any specific i, just before iteration, the subarray A[i...i-1] contains the elements present initially in the subarray B[0....i-1] and the subarray B[0.....i-1] contains the elements initially present in the subarray A[0.....i-1]. For this specific i, the for loop does nothing but swap the ith elements of the two arrays. Thus after this iteration of the loop, the subarrays A[0....i] and B[0....i] contains the swapped elements.

Step 3- Termination :-

The loop terminates when i becomes equal to n. At this point of time the arrays A[0...n-1] and B[0....n-1] contains the swapped elements. Thus the array A contains the elements that were present in B and B contains the elements that were initially present in A. Thus we have accomplished what we wanted to do. The elements of both the arrays have been swapped.

Thus the loop invariants used by us are correct as they verify the correctness of the above algorithm.

Related Questions

Navigate

• Browse (All)
• Browse L
• Subjects

---

---

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