Question 1 (6 points) Use the Master theorem to solve the following recurrence relations if the Master theorem is applicable. If it is not applicable, state why it is not applicable. You do not have to solve the recurrence relation if the Master theorem does not apply. 1. T(n) = 2T (n/4) + Vn 2. T(n) = 9T(n/3) + n 3. T(n) = 16T(n/4) + n! 4. T(n) = 4T (2n) + Vn Question 2 (8 points) Let X be a kn x n matrix and Y by an n x kn matrix, for some integer k. 1. Describe an algorithm that computes the product XY using Strassen's algorithm as a subroutine, i.e., use it as a black- box without modifying it. Only describe your algorithm in words; pseudo-code is not required. Justify your answer, i.e., argue that your algorithm does compute XY correctly. Establish its running time. 2. Repeat part (a) for computing the product YX. Question 3 (6 points) In the selection problem discussed in class, we used an algorithm that computes the median of 5 and showed that it works in a worst-case linear time. 1. Repeat the problem using the median of 3 and argue that it does not work in linear time. 2. Repeat the problem using the median of 7 and show that it works in a linear time