Consider the following program specification: Input: An integer n > 0 and an arr

Question

Consider the following program specification:

Input: An integer n > 0 and an array A[0..(n - 1)] of n integers.

Output: The smallest index s such that A[s] is the smallest value in A[0..(n - 1)].

For example, if n = 8 and A = [ 4, 8, 1, 3, 1, 5, 4, 7 ] (so A[0] = 4, A[1] = 8, etc.), then the program would return 2, since the smallest value in A is 1 and the smallest index at which 1 appears is index 2.

Consider the following implementation:

In the implementation above, line numbers are given so you can refer to specific lines in your answers and is used to indicate assignment.

Use induction to establish the following loop invariants right before the while test in line (4) is executed:

Prove the correctness of the implementation by arguing

partial correctness and

indexOfMin(n, A) (1) i 1 (2) m A[0] (3) s 0 (4) while i < n (5)      if A[i] < m then (6)           m A[i] (7)           s i (8)      end (9)      i i + 1 (10) end (11) return s

Explanation / Answer

(iii) m = min A[0..(i-1)]

We have to take min for entire loop, we cant compare A[0] all the time.

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---