Consider the following algorithm, which returns the index of the maximum value in an array of integers.
The function accepts a list A[1…n] with n items
myfunc(A, n):
i = 1
j = n
while (i < j):
if (A[i] > A[j]):
j = j – 1
else:
i = i + 1
### Loop Invariant ###
return i
What is an appropriate loop invariant for this algorithm at the point specified?

Question

Consider the following algorithm, which returns the index of the maximum value in an array of integers. 
 The function accepts a list A[1…n] with n items 
 myfunc(A, n): 
     i = 1 
     j = n 
     while (i < j): 
         if (A[i] > A[j]): 
             j = j – 1 
         else: 
             i = i + 1 
         ### Loop Invariant ### 
     return i 
 What is an appropriate loop invariant for this algorithm at the point specified?

Answer

The maximum value for A[1..n]  is equal to the maximum value for A[i…j-1] and i is less than j

Answer

The maximum value for A[1..n]  is equal to the maximum value for A[i+1…j] and i is less than j

Answer

The maximum value for A[1..n]  is equal to the maximum value for A[1…i]

Answer

The maximum value for A[1..n]  is equal to the maximum value for A[i…j] and j is greater than or equal i

Answer

The maximum value for A[1..n]  is equal to the maximum value for A[1…j]

Crowdly

Consider the following algorithm, which returns the index of the maximum value i...

Want instant access to all verified answers on learning.monash.edu?