Throughout this assignment, adopt the following notation: a || B denotes the concatenation of lists a and B (in this order); e denotes the empty string; len(s) 20 denotes the length (number of characters) on string s; minx(A[a...b]) denotes the index (in range [a...b]) of the minimum odd element from list Ala...b); 4 =a+L(b-a)/3] and 12 = b-[(b-a)/3] denote the indices at one third and two thirds the way from a to b, respectively; pairsort(X,Y) denotes either Y|X (if X and Y are both odd and X > Y) or X | Y (other- wise). Consider the problem of sorting the odd elements in a list of integers while keeping the even ones unchanged in their original places. Sort the odd elements in a list (ODDSORT) Input: A[1...n] a list of integers. Output: List A'[l...n] such that A'[i] = A[i] if A'[i] is even, and A'[i] = A'[j] for all Isis jsn such that A'[i] and A'[j] are both odd. 3. (1 point) Below is another self-reduction for the ODDSORT problem. State a recursive algo- rithm using pseudocode for solving the ODDSORT problem based on this self-reduction. pairsort(A[a], A[b]) if a b if ba+1 if b> a+1 SOS(A[a...b]) = --- with A' SOS(A[a... 121 A[12 +1...b) A'la... t|| SOS(A' [11+1...b]) SOSIA" a... 121 | A" 12 +1...b) Throughout this assignment, adopt the following notation: a || B denotes the concatenation of lists a and B (in this order); e denotes the empty string; len(s) 20 denotes the length (number of characters) on string s; minx(A[a...b]) denotes the index (in range [a...b]) of the minimum odd element from list Ala...b); 4 =a+L(b-a)/3] and 12 = b-[(b-a)/3] denote the indices at one third and two thirds the way from a to b, respectively; pairsort(X,Y) denotes either Y|X (if X and Y are both odd and X > Y) or X | Y (other- wise). Consider the problem of sorting the odd elements in a list of integers while keeping the even ones unchanged in their original places. Sort the odd elements in a list (ODDSORT) Input: A[1...n] a list of integers. Output: List A'[l...n] such that A'[i] = A[i] if A'[i] is even, and A'[i] = A'[j] for all Isis jsn such that A'[i] and A'[j] are both odd. 3. (1 point) Below is another self-reduction for the ODDSORT problem. State a recursive algo- rithm using pseudocode for solving the ODDSORT problem based on this self-reduction. pairsort(A[a], A[b]) if a b if ba+1 if b> a+1 SOS(A[a...b]) = --- with A' SOS(A[a... 121 A[12 +1...b) A'la... t|| SOS(A' [11+1...b]) SOSIA" a... 121 | A" 12 +1...b)