I Need help in solving a) part of the problem. Below are the slides mentioned in the problem.

Bubble sort is a popular, but inefficient, sorting algorithm. It works by repeatedly swapping adjacent elements that out of order. BUBBLESORT(A) 1. for i = 1 to A.length - 1 2. for j = i + 1 to A.length 3. if All 0 and A[i]> key A[i+1] = A[i] A[j+1.. n) corresponds to the remaining pile of i=i-1 cards on the table A[i+1] = key dimitriono In fact, A[1..j-1] are the elements originally in positions 1 through/ - 1) but now in sorted order. These properties are formally called loop invariant Maintenance: o Before an iteration, A[1 ..j-1] is already sorted o The body of for loop moves A[j-1], A[j-2), A[j-3) ... by one position to the right, until it finds the proper position for A[j] (Line 4 -- 7) o At which point it inserts the value of A[j] (Line 8) o Now the subarray A[1 .. )) consists of the elements originally in A[1 .. j], but in sorted order. o Incrementing for the next iteration then preserves the loop invariant cimitroroo INSERTION-SORT(A) 1. for j = 2 to A.length key = A[] // Insert A[] into the sorted sequence A[1 ..j-1] i=j-1 while i >0 and A[i]> key A more formal examination requires us to show a A[i+1] =A[i] loop invariant for the while loop as well i=i-1 A[i+1] = key Loop invariant: At the start of each iteration, the subarray Ap..k - 1) contains the k-pl smallest elements of L[1..ni + 1] and R[1..n2 + 1], in sorted order. L[i] and R[j] are the smallest elements of their arrays that have not been copied back into A. Analyze its correctness Initialization: Prior to the first iteration, k = p. o Ap..k - 1] is empty, which contains O smallest elements from L and R. Since i = j = 1, L[i] and Rujare the smallest elements. 12. for k=p tor 13. if L[i] S RU] 14. A[k] = L[i] i=i+1 else A[k] = RUD j=j+1 17