Question

Consider the following program specification:

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

Output: The largest index b such that A[b] is the largest value in A[0..(n – 1)].

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

Consider the following implementation:

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

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

Part a (18 points)

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

1. 0< i ≤ n
2. m = A[b]
3. m = max A[0 .. (i – 1)]   (i.e., m is the maximum value in that appears in the array A between indices 0 and i – 1, inclusive)
4. b is the largest index at which max A[0 .. (i – 1)] appears

Hints and tips:

• Use only one induction proof and prove each of the four parts of the invariant in your base case and inductive step.
• Since the program has an if statement, your analysis will have to take into consideration the case that the if condition is true and the case that the if condition is false.
• You may assume that i and b will always be integers (i.e., you don't have to prove this).

Part b (7 points)

Prove the correctness of the implementation by arguing

1. partial correctness and
2. termination.

Answer 1

Part A.

Here we can see that we have Array of Value and have to find max index of max value in Array.

Now, As program is is already implementated. We have to proof induction for this.

1. 0< i ≤ n------------------>> This is Where we will search for all elements
2. m = A[b]-------------->> Once we find the max element store it in m
3. m = max A[0 .. (i – 1)]   (i.e., m is the maximum value in that appears in the array A between indices 0 and i – 1, inclusive)------------------>>This max element will reside in index between 0 to i-1.
4. b is the largest index at which max A[0 .. (i – 1)] appears----------------->>then finally max index will be in between 0 to i-1.

For, Prooving this let's assume.

Our First target will be to find out max element in array. And when we find out that this max element at b index then, we will search for 0 to b.

In fact, largest index will be at index b only.

Becouse of element we increase the index and element is find out by this then that index will be largest index.

However , one conflict my arrive at we have max element more then one value in array.

That time there is possiblity of have two index as result but we will choose bigger one in that.

So, we undestand that the comparion we are doing in if clause is most important.

Once 0 to n-1 loop end, always max element will be with largest index.

So, 0 to i-1 index max index will be i-1 as b.

Part B.

Here, Correctness of the implementation will be depands on data of input array.

If Array contains negative value then this program will not work correctly. For all postive integer it will work fine.

For Termination it will always terminate with finite value of n.