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 A[a...b); 4 =a+[(b-a)/3] and 12 = b-f(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 lsis jsn such that A'[i] and A'lj] are both odd. 11. (bonus: 1 point) Slate a recurrence that expresses the worst case for bad pivots. 12. (bonus: 1 point) State another recurrence that expresses the worst case for good pivots. 13. (bonus: 3 points) Prove by induction that a suitable combination of the two recurrences above expressing the expected worst case for any pivot is (nlogn). Grading of bonus questions: Correctness and precision are of utmost importance. Use formal proof structures for the Big-Theta bounds. As always, you will be docked points for errors in your math, disorganization, lack of clarity, or incomplete proofs. 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 A[a...b); 4 =a+[(b-a)/3] and 12 = b-f(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 lsis jsn such that A'[i] and A'lj] are both odd. 11. (bonus: 1 point) Slate a recurrence that expresses the worst case for bad pivots. 12. (bonus: 1 point) State another recurrence that expresses the worst case for good pivots. 13. (bonus: 3 points) Prove by induction that a suitable combination of the two recurrences above expressing the expected worst case for any pivot is (nlogn). Grading of bonus questions: Correctness and precision are of utmost importance. Use formal proof structures for the Big-Theta bounds. As always, you will be docked points for errors in your math, disorganization, lack of clarity, or incomplete proofs
