Throughout this assignment, adopt the following notation: - AB denotes the concatenation of lists A and B (in this order), and is assumed to take O(1) time to execute; - denotes the empty string; - len (s)0 denotes the length (number of characters) on string s, and is assumed to take O(1 ) time to obtain; - minpx(A[ab]) denotes the index (in range [ab]) of the smallest prime element from list A[ab], and is assumed to take linear time (i.e. O(n) where n=ba+1 ) to execute; - t1=a+(ba)/3 and t2=b(ba)/3 denote the indices at one third and two thirds the way from a to b, respectively; - pairsort (X,Y) denotes YX if integers X and Y are both prime and X>Y, otherwise it denotes XY. - is_prime (X) is a Boolean function that determines whether or not X is prime (that is, is_prime (X) is true if, and only if, the only positive integers divisors of X are 1 and X itself. - is_sqr(n) is a Boolean function that determines whether or not n is a perfect square (that is, is_sqr(n) is true if, and only if, n is an integer of form n=r2 for some integer r ). Consider the problem of sorting only the prime elements in a list of integers while keeping the composite ones unchanged in their original places: 1. (1 point) Below is a self-reduction for that problem, where we define k=minpx(A[ab]), the position of the smallest prime on A[a..b]. State a recursive algorithm (using pseudocode) for solving the SORTPRIMES problem based on this self-reduction. Hint: call is_prime (X) where needed, and don't forget to compute k explicitly. Also, pay attention to the opening and closing parentheses and brackets! SCHOOL OF ENGINEERING AND TECHNOLOGY SP(A[a..b])=AA[a]SP(A[a+1b])A[k]SP(A[a+1k1]A[a]A[k+1b])ifa>bifabandeitherA[a]iscompositeora=kifabandA[a]isprimeanda