Test Algorithm Just list the ones that are always true Merge Sort Question Provi

Question

Test Algorithm

Just list the ones that are always true

Merge Sort Question

Provide Clear Explanation and do all parts

Consider the following pseudocode: Algorithm 1: Test Alg (A) Input: A is an array of real numbers, indexed from 1 to n 1 n length (A) 2 for j 1 to (LI) do Ak Ak Which of the following invariants are true at the end of every iteration of the for loop? i. The sub-array A(1...jl contains its original contents in the same order ii. The sub-array A 1 1 contains the original contents of sub-array AI(m 1-j) n in reverse order iii. The sub-array A1...j contains its original contents in reverse order. iv. The sub-array A(n 1 -j).. n contains its original contents in the same order v. The sub-array A (n +1-j)... n] contains the original contents of sub-array A10 in reverse order vi. The sub-array A(n 1 -j) n contains its original contents in reverse order. Just list the ones that are always true.

Explanation / Answer

Answer - 1

   loop invariant - "The subarray A[1...J] contains the original contents of the subarray A[(n+1-J)...n] in reverse order"
       is always true.
      
   Here, J = (n / 2) whenever n is an even number and J = ((n - 1) / 2) whenever n is a odd number
  
   Example -
           n = 10 then J = 5 and n = 11 then J = 5
          
   Here the for loop is used to exchange the value of A[j] and A[k] without using another third example
  
   Example -
           initially A[j] = 10 , A[k] = 25
          
           After A[j] <- A[j] + A[k] , A[j] = 35
          
           After A[k] <- A[j] - A[k] , A[k] = 10
          
           After A[j] <- A[j] - A[k] , A[j] = 25
          
           At the end, A[j] = 25 , A[k] = 10
  
   In this loop invariant j goes from 1 to J and k goes from n to (n+1-J)
       and exchange A[j] and A[k]
      
   Thus following exchange operations take place -
       exchange A[1] and A[n]
       exchange A[2] and A[n-1]
       ...
       exchange A[j] and A[n+1-J]
      
   At the end of loop invariant the subarray A[1...J] contains the original contents of the subarray A[(n+1-J)...n] in reverse order
  
   Example -
       If n = 10 then J = 5 , (n+1-J) = 6 , the following exchange operations take place -
           exchange A[1] and A[10]
           exchange A[2] and A[9]
           ...
           exchange A[5] and A[6]
          
       If n = 11 then J = 5 , (n+1-J) = 7 , the following exchange operations take place -
           exchange A[1] and A[11]
           exchange A[2] and A[10]
           ...
           exchange A[5] and A[7]

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

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