Question Four a. Show that the worst-case and average-case time complexities for the number of assignments of records performed by the Exchange Sort algorithm (Algorithm 1.3) are given by W(n)=23n(n1)andA(n)=43n(n7). b. Write an algorithm (pseudocode) that sorts a list of n elements in nonincreasing order by finding the largest and smallest elements and exchanges those elements with the elements in the first and last positions. Then the size of the list is reduced by 2 , excluding the two elements that are already in the proper positions, and the process is repeated on the remaining part of the list until the entire list is sorted. Analyze your algorithm and show the results using order notation. (Hint: Use arguments) c. Find an optimal circuit for the weighted, direct graph represented by the following matrix W. Show the actions step by step. W=034610801166137072188100120107110 Algorithm 1.3 Exchange Sort Problem: Sort n keys in nondecreasing order. Inputs: positive integer n, array of keys S indexed from 1 to n. Outputs: the array S containing the keys in nondecreasing order. void exchangesort (int n, keytype S[] ) \{ index i,j; for (i=1;i