Question

Let A[1..n] be an array with n elements. Consider the Count-Occurrence algorithm with the pseudocode below. Count-Occurrence(A, n, k). count 0 for j = 1 to n if A[j] ==k count = count+1 print count Which of the following is the correct loop invariant for the for loop? At the start of each iteration jof the for loop, count represents the number of times that k occurs in the subarray A[1.j]. At the start of each iteration of the for loop,count represents the number of times that koccurs in the subarray Alj...n). O At the start of each iteration of the for loop, count represents the number of times that k occurs in the subarray A[j-1...n). At the start of each iteration jof the for loop, count represents the number of times that k occurs in the subarray A[1..j-1].

Answer 1

Answer :

The correct loop invariant is 4th option :

At the start of each iteration j of the for loop, count represents the number of times that k occurs in the subarray A[1..j-1].

Explanation :

At the start of each iteration j , the count is what upto the previous iteration j-1 (means the count represents the number of times that k occurs in the subarray A[1..j-1] ), but by the end of the j th iteration count is incremented if condition is true i.e., A[j] == k. It means by the end of the j th iteration the count represents the number of times that k occurs in the subarray A[1..j-1].

Tracing :

lets take an array A of size 8. therefore n = 8

A = { 2, 4, 2, 2, 1, 2, 9, 3 }

let k = 2;

iteration-1: j=1, count=0, (start of 1st iteration)

A[1] == k

count = 1 (by the end of 1st iteration count is incremented because condition is true.)

iteration-2: j=2, count=1, (start of 2nd iteration count is still previous iteration value)

A[2] != k

count = 1 (by the end of 2nd iteration count is not incremented because condition is false.)

iteration-3: j=3, count=1, (start of 3rd iteration)

A[3] == k

count = 2 (by the end of 3rd iteration count is incremented because condition is true.)

iteration-4: j=4, count=2, (start of 4th iteration the count is still representing the previous value i.e., number of times that k occurs in the subarray A[1..j-1] )

A[4] == k

count = 3 (by the end of 4th iteration count is incremented because condition is true.)