Problem 2 Consider the following program specification Input

Problem 2

Consider the following program specification:

Input: An integer n 0, an array A[0..n - 1] of integers, and an integer val.

Output: -1 if val does not appear in A, otherwise the smallest index i such that A[i] = val.

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.

A). Use induction to establish the following loop invariant right before the while test in line (2) is executed:
0 i n and val does not appear in A[0..(i - 1)] (with the convention that A[0.. -1] denotes an empty array).

B). Prove the correctness of the implementation by arguing

partial correctness and

termination.

Solution

Answer to Problem 2 Bit A

The algorithm searches the position of val in the array A[0---n-1]

The while loop checks the array A[0. . . (i-1)] before checking the value ‘val’ in A[i] (position i). the value val is searched in ‘i’ th position means the array A with position [0… i-1] does not contain ‘val’

SO as the right before the test in line 2, When i=0, Array element A[0..i-1] that is A[0..-1] which is empty. so the val does not appear in A[o..n-1] :

Loop invariant is true prior to the execution loop;

Answer to Problem 2 Bit B

To prove the correctness of the implementation, following loop invariant must be satisfied.

Initializtion: The algorithm is true Prior to the the 1^st iteration of loop,

Ass aid earlier, Prior to the first iteration of loop.At I=0,val does not appears in Array A[0..i-1]=A[0..-1] .

Maintanace: If it is true before one iteration, it remains true before next iteration.

Lets assume If for some value of i=k, before any iteration. This means the val does not appeared in A[0..k-1]. And i=i+1 if and only if A[k]!=val,(in next iteration),When i=k+1, the val does not appear A[0..k].

Termination: If loop terminates, the invariant gives us the property that helps us to show that the algorithm is correct .

if the algorithm terminated due to i=n, I,e A[0.. i-1] which is A[0..n-1] which is the original array, does not contain the value ‘val’ .

The algorithm satisfies Above 3 loop invariant, So the algorithm is correct.