1.) (5 points each) Solve the following recurrences using the Master Theorem. You must identify the values of a, b, and d, and state which case you are using. All answers must be in big-O notation.
(a.) T (n) = 3T (n2 ) + n
(b.) T (n) = 4T (n2 ) + 7n2
(c.) T (n) = T (n3 ) + 25
(d.) T (n) = 5T (n5 ) + n5
(e.) T (n) = 5T (n2 ) + 4n2
Solution:
(f.) T (n) = 8T (n3 ) + 2n2
2.) (15 points each) Suppose we have an array A = [a, b, c, ..., y] of 25 integers. In the process of finding the median of medians, we form the following 5 subarrays, each of which is sorted:
[d, c, b, e, a]
[i, f, h, j, g]
[l, m, k, n, o]
[p, s, q, r, t]
[w, x, v, u, y]
We take the medians from the 5 subarrays (i.e. b, h, k, q, and v), and we collect them into a new sorted array [k, h, q, b, v]. Since the median of this new sorted array is q, we can say the median of medians is q.
(a.) Which elements of the original array A are guaranteed to be less than or equal to q? List them all and briefly justify your answer.
(b.) Which elements of the original array A are guaranteed to be greater than or equal to q? List them all and briefly justify your answer.
(c.) Is q a good pivot? Justify your answer.
3.) (15 points each) Suppose we have an array, A, containing n distinct integers. We are also given as input, a lower bound l and an upper bound u. Provide a Divide & Conquer algorithm to find the number of elements in A between l and u, inclusive, under each of the following conditions. Make sure to provide reasoning for your algorithm and give the time complexity with proof (using the Master Theorem).
(a.) Condition 1: A is an unsorted array
(b.) Condition 2: A is a sorted array
Solution:
