Please type your answer! Do not copy the handwriting image from the other same questions!

Exercise 3 (50 points) Loop Invariant Consider the algorithm getIndexMinimum(A,k) that takes a sequence A as an input and returns the index of the smallest number (minimum) in the range [k-A.length] in Sequence A. For example, let A={100,2,14,5,22,7}. getlndexMinimum (A,3) will return 4 because 4 is the index of the element 5 and 5 is the smallest number in A in the range [3-6]. Consider the following sorting algorithm that sorts a sequence A in increasing order: Sort-Array (A) for wi=1 to A.length IndexMin = get IndexMinimum (A, /I swap A [i]] and A[IndexMin] buffer =A[ IndexMin ] A[ IndexMin ]=A[i] A[i]= buffer The objective is to prove that the above sorting algorithm is correct. Consider getting inspiration from the textbook in Section 2.1: the author shows that the Insert Sort algorithm is correct using loop invariants. Their proof should help you with this exercise. It is expected and strongly advised that you follow their steps. Advice: get familiar with Sort-Array by executing the algorithm Sort-Array(A) when A{100,3,20,7} I) (4 points) Express the property that Sort-Array (A) must satisfy to be correct: 2) (8 points) List four loop invariants (even if they are not that helpful for our ultimate proof of correctness of Sort-Array). Specify whether your loop invariant applies before or after the iteration. 3) (I0 points) Propose a loop invariant for the outer loop that is the closest to our ultimate objective: Sort-Array is correct. 4) Use the three steps: a. (6 points) Initialization b. (I4 points) Maintenance