Consider the following program specification Input An intege

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

i) partial correctness and

ii) termination.

Solution

a).

i. base case i=0; where n=0;

then by line 2 i<n is false.

return -1 with loop terminate.

ii.

a. partial correctness

Loop Invariant: If the loop body is exectuted j times or more , then after j times of execution of the loop body i = j; 0 <= i <= n;
A[m] not equals to k for 0 <= h < i
Proving the Loop Invariant: use induction on j Base Case (j = 0): before first execution of loop body we have i = 0 loop invariant holds
(conditions on i, no values of h such that 0 = h < 0)

Inductive hypothesis: assume that, if the loop iterates j times, then the loop invariant holds for initial value of i = j.
we need to show that if the loop iterates a [j + 1] time, then the loop invariant holds for new value of i = j + 1

When the loop test fails, the loop invariant holds and
either i = n or A[i] = k

Case 1: (i >= n): loop invariant implies that A[h] not equals to k also for 0 <= h < n,
so k is not in A and KeyNotFoundException
is thrown
Case 2: (i < n): loop invariant implies that A[i] = k and i is returned

Conclusion: postcondition is satisfied in either case, so linearSearch is paritally correct

b). Termination: f(n, i) = n - i Proving the Loop Variant: f(n, i) is a decreasing integer function because integer i
increases after each loop body execution f(n, i) = 0 when i = n, loop terminates (worst case) when i = n