1. Design a recursive algorithm MySelect(A,k) for the Select problem that was discussed in class. MySelect should call MySelect recursively on smaller arrays with 1 less element. Write down its base case, recurrence relation, and solve it. MySelect should not use more than constant additional space, and should not modify the array.

T(n) = 2T(n-1) + O(1) = 2^n

2. Solve the recurrence for Karatsuba's algorithm using the identity bc + ad = (a+b)(c+d) - ac - bd

Hint: Look at the subsection "Ignoring Floors and Ceilings Is Okay, Honest"

3. JE-9 (a)
"Imagine a problem where you have to sort a stack of 20 pancakes. And suppose you magically knew how to sort top k pancakes, for any k=2...19. Can you use this superpower to sort your stack?"

First try this problem where you can inspect the pancakes to compare their sizes?

Then try this problem where all you can do is flip, except for the ability to check the sizes of the top 2 pancakes.

4. JE-13
Imagine a problem where you have to count the number of inversions in a 20 element array. Suppose you magically can figure out how to count the number of inversions in ***any*** 10-sized array. Can you use this superpower for your task, maybe with some additional work? You should get stuck (but wait until you are stuck). Now suppose you magically knew (a) how to count the number of inversions in any 10-sized array and (b) the sorted version of any 10-sized array. Can you use your new found ability to perform your task?