4. Let A = [a1, a2, . . . , an] be an array of numbers. Lets define a reverse as a pair of distinct indices i, j {1, 2, . . . , n} such that i aj ; i.e., ai and aj are out of order. For example - In the array A = [1, 3, 5, 2, 4, 6], (3, 2), (5, 2) and (5, 4) are the only reverses i.e. the total number of reverses is 3. (a) Let A be an arbitrary array of length n. At most, how many reverses can A contain in terms of the array size n? Explain your answer with a short statement.

(b) We say that A is sorted if A has no reverses. Design a sorting algorithm that, on each pass through A, examines each pair of consecutive elements. If a consecutive pair forms a reverse, the algorithm swaps the elements (to fix the out of order pair). For instance, if your array A was [4,2,7,3,6,9,10], your first pass should swap 4 and 2, then compare (but not swap) 4 and 7, then swap 7 and 3, then swap 7 and 6, etc. Formulate pseudo-code for this algorithm, using nested for loops. Hint: After the first pass of the outer loop think about where the largest element would be. The second pass can then safely ignore the largest element because its already in its desired location. You should keep repeating the process for all elements not in their desired spot.

(c) Your algorithm has an inner loop and an outer loop. Provide the useful loop invariant (LI) for the inner loop.You dont need to show the complete LI proof.

(d) Assume that the inner loop works correctly. Using a loop-invariant proof for the outer loop, formally prove that your pseudo-code correctly sorts the given array. Be sure that your loop invariant and proof covers the initialization, maintenance, and termination conditions.

4. Let A = [a1, a2, ..., an] be an array of numbers. Let's define a 'reverse' as a pair of distinct indices i, j e {1,2, ..., n} such that i a;; i.e., a; and a; are out of order. For example - In the array A = [1, 3, 5, 2, 4, 6], (3, 2), (5, 2) and (5, 4) are the only reverses i.e. the total number of reverses is 3. () Let A be an arbitrary array of length n. At most, how many reverses can A co- tain in terms of the array size n? Erplain your answer with a short statement. (b) We say that A is sorted if A has no reverses. Design a sorting algorithm that, on each pass through A, examines each pair of consecutive elements. If a consecutive pair forms a reverse, the algorithm swaps the elements (to fix the out of order pair). For instance, if your array A was [4,2,7,3,6,9,10], your first pass should swap 4 and 2, then compare (but not swap) 4 and 7, then swap 7 and 3, then swap 7 and 6, etc. Formulate pseudo-code for this algorithm, using nested for loops. Hint: After the first pass of the outer loop think about where the largest element would be. The second pass can then safely ignore the largest element because it's already in it's desired location. You should keep repeating the process for all ele- ments not in their desired spot. (c) Your algorithm has an inner loop and an outer loop. Provide the "useful" loop invariant (LI) for the inner loop. You don't need to show the complete LI proof. (d) Assume that the inner loop works correctly. Using a loop-invariant proof for the outer loop, formally prove that your pseudo-code correctly sorts the given array. Be sure that your loop invariant and proof covers the initialization, maintenance, and termination conditions