Problem $4.$ Algorithmic Correctness $(10$ points$)$

It's here again... our algorithm for LINEARSEARCH.

LINEARSEARCH$(A,n,$key$)$

Prove that LINEARSEARCH is correct by showing that the following loop invariant: At the

start of each iteration of the for loop, the subarray $A[1..i-1]$ consists of the elements in $A$

that are not equal to the key. Use the loop invariant proof structure of $(1)$ initialization, $(2)$

maintenance, and $(3)$ termination.

Solution: