Recall the Insertion$-$Sort algorithm discussed in the lecture:

In the lecture, you have seen a correctness proof of the algorithm based on the following loop invariant

for the $($outer$)$ for loop:

Let $A_j[1,$dots,$n]$ denote the array at the beginning of iteration $j($end of iteration $j-1).$ We have that

$A_j[1,$dots,$j-1]$ stores the same values as $A[1,$dots,$j-1]$ but in sorted order, while $A_j[l]=A[l]$

for $jln.$

In this problem, you will fill in a bit more detail in the proof, by also introducing a loop invariant for the

$($inner$)$ while loop. You will use the following loop invariant:

Let $A_{j,i}[1,$dots,$n]$ denote the array at the beginning of iteration $i$ of the inner loop $($for $0ij-1).$

Then:

If the loop executes with value $i+1,$ then

$A_{j,i}[1,$dots,$i]=A_j[1,$dots,$i],$ and

If $i+2j,$ then $A_{j,i}[i+2,$dots,$j]=A_j[i+1,$dots,$j-1]$ and $i+1A_{j,i}=A_{j,i+1}ii=j-1ij1jn{A}_j[j].$

Otherwise $(if$ the while loop terminates before reaching value $i+1),$ then $A_{j,i}=A_{j,i+1}.$

Solve the following tasks:

Prove the while loop invariant above using induction over $i.$ Start your base case $ati=j-1$ and

use backwards induction $to$ show that the claim holds for all smaller $i.(Prove$ this for $an$ arbitrary

value $ofj,$ where $1jn.)$

Use the inner loop invariant $to$ show the induction step $of$ the outer loop invariant.