Exercise $2(70$ points$)$ Loop Invariant

Consider the algorithm getIndexMaximum$($A$,$k$)$ that takes a sequence A as an input and returns the

index of the largest number $($maximum$)$ in the range $[$k$-$A$.$length$]$ in Sequence A$.$

For example, let A $=\{100,2,14,5,22,7\}.$ getIndexMaximum$($A$,3)$ will return $5$ because $5$ is the index of

the element $22$ and $22$ is the largest number in A in the range $[3-6].$

Consider the following sorting algorithm that sorts a sequence A in decreasing order:

Sort$-$Array$($A$)$

for i $=1$ to A$.$length

IndexMax $=$ getIndexMaximum$($A$,$i$)$

$//$ swap A$[$i$]$ and A$[$IndexMin$]$

buffer $=$ A$[$IndexMax$]$

A$[$IndexMax$]=$ A$[$i$]$

A$[$i$]=$ buffer

The objective is to prove that the above sorting algorithm is correct. Use the textbook in Section $2\mathrm{.}1$:

the authors show that the InsertSort 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 in Section $2\mathrm{.}1.$

Advice: get familiar with Sort$-$Array by executing the algorithm Sort$-$Array$($A$)$ when A $=\{7,3,20,100\}$

$1)(5$ points$)$ Express the property that Sort$-$Array$($A$)$ must satisfy to be correct:

$2)(12$ 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)(15$ 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$.(8$ points$)$ Initialization

b$.(18$ points$)$ Maintenance

c$.(12$ points$)$Termination