Hello, I need help with question 2. I do not need answers for question 1, it is there for more info. Thank you!

Adding up the contributions of these four cases, we obtain the probability that the median of the 3 se- lected items lies in set B. (2) Shearsort. [a] When the numbers being sorted are restricted to the set {0,1), we showed that the end state consists of at most one mixed row of Os and 1s. Derive the maximum number of steps required (each row and each column sort counts as a separate single step) to execute Shearsort, assuming an 8 x 8 array. [b] The maximum number of steps required to sort an arbitrary set of numbers is no greater than the maxi- mum required to sort an arbitrary sequence of elements from {0, 1). How would you show that? (Just saying "O-1 Lemma" is not enough: you need to show more detail in your argument.) (3) Consider the recurrence (here l is a whole number greater than 1): T(n) = { 21(1/2) +n if n = Prove by induction that the solution of this recurrence is Tan) = n lg n. (1) Quicksort. In this question, we will analyze picking the pivot by taking 3 numbers from the array at random and then taking the median of these three. The question is the probability that this pivot is close to the real median of the array. Suppose we define three sets, A, B, and C. A consists of the a smallest numbers in the array to be sorted, C consists of the c largest numbers to be sorted and B is the rest of them: it has b = n-a-c numbers, where n is the length of the array to be sorted. Assume that min{a,b,c) > 3. Derive an expression for the probability that the middle of 3 elements randomly picked (without replace- ment) from the array is in set B. We started the process in class by looking at one of the cases; in this question, you will complete it. We'll need some notation for convenience. Denote by (i, j, k) the event that we select i items from A, j from B and k from C, all without replacement. The cases which lead to the median falling in set B are: (1,1,1),(0,2,1),(1,2,0), (0,3,0). We went over (1,1,1) in class. Follow these steps. (If you are reasonably familiar with probability, you can write down the answer directly, but if not, it helps to go through the steps one by one.)