Consider the following pseudocode: A is an array of real numbers, indexed from 1
ID: 3781928 • Letter: C
Question
Consider the following pseudocode: A is an array of real numbers, indexed from 1 to n n leftarrow length (A); for j leftarrow to ([n/2]) do k = n + 1 - j; A [j] leftarrow A[j] + A[k]; A[k] leftarrow A[j] - A[k]; A[j] leftarrow A[j] - A[k]; Which of the following invariants are true at the end of every iteration of the for loop? The sub-array .A[1...j] contains its original contents in the same order The sub-array A[1...j] contains the original contents of sub-array A[(n + 1 - j)...n] in reverse order. The sub-array A[1...j] contains its original contents in reverse order. The sub-array A[(n + 1 - j)...n] contains its original contents in the same order. The sub-array A[(n+1 - j)...n] contains the original contents of sub-array A[1...j] in reverse order. The sub-array A[(n + 1 - j)...n] contains its original contents in reverse order.Explanation / Answer
Only option 2 and 5 are TRUE.
Explanation:
This algorithm, after the execution of the final iteration, will give us an array which is in reverse order.
For example, if original array is {2,3,4,5,6}. Then, after the final iteration, the array will be {6,5,4,3,2}.
After the first iteration: A[1]=original value of A[n], and A[n]=original value of A[1].
After the second iteration: A[2]=original value of A[n-1], and A[n-1]=original value of A[2].
After |n/2| th iteration: A[|n/2|]=original value of A[n-(|n/2|-1)], and A[n-(|n/2|-1)]=original value of A[|n/2|]
Now, let's examine all the options one by one.
Option 1 (FALSE): The sub-array A[1...j] contains its original contents in the same order. This is false, as the value of the first element is the value of the last element and so on.
Option 2 (TRUE): The sub-array A[1...j] contains the original contents of sub-array A[(n+1-j)...n] in reverse order. This is true. For example, take an array of length 10,i.e. A[10]={1,2,3,4,5,6,7,8,9,10}. Now, after second iteration, the array will become {10,9,3,4,5,6,7,8,2,1}. That means, after second iteration, the sub-array A[1...2] contains the original contents of sub-array A[9...10] IN REVERSE ORDER.
Option 3 (FALSE): The sub-array A[1...j] contains its original contents in reverse order. This can not be true, as already explained above (in option 2).
Option 4 (FALSE): The sub-array A[(n+1-j)...n] contains its original contents in the same order. This is again false. Considering the same example as discussed in option 2, after the second iteration, contents of A[9...10] are not their original contents.
Option 5 (TRUE): The sub-array A[(n+1-j)...n] contains the original contents of sub-array A[1...j] in reverse order. This is true (see example in option 2).
Option 6 (FALSE): The sub-array A[(n+1-j)...n] contains its original contents in reverse order. This is false. As in example (see option 2), A[9...10] has the contents of A[1...2] in reverse order.