Description
1. (20 pts total) Solve the following recurrence relations using any of the following methods: unrolling, tail recursion, recurrence tree (include tree diagram), or expansion. Each each case, show your work. (a) T(n) = T(n−2) + C n if n 1, and T(n) = C otherwise (b) T(n) = 3T(n−1) + 1 if n 1, and T(1) = 3 (c) T(n) = T(n−1) + 3n if n 1, and T(1) = 3 (d) T(n) = T(n1/4) + 1 if n 2 , and T(n) = 0 otherwise
2. (10 pts) Consider the following function:
def foo(n) { if (n 1) { print( ’’hello’’ ) foo(n/3) foo(n/3) }}
In terms of the input n, determine how many times is “hello” printed. Write down a recurrence and solve using the Master method.
3. (30 pts) Professor McGonagall asks you to help her with some arrays that are raludominular. A raludominular array has the property that the subarray A[1..i] has the property that A[j] A[j + 1] for 1 ≤ j < i, and the subarray A[i..n] has the property that A[j] < A[j + 1] for i ≤ j < n. Using her wand, McGonagall writes the following raludominular array on the board A = [7,6,4,−1,−2,−9,−5,−3,10,13], as an example.
(a) Write a recursive algorithm that takes asymptotically sub-linear time to find the minimum element of A.
1
(b) Prove that your algorithm is correct. (Hint: prove that your algorithm’s correctness follows from the correctness of another correct algorithm we already know.) (c) Now consider the multi-raludominular generalization, in which the array contains k local minima, i.e., it contains k subarrays, each of which is itself a raludominular array. Let k = 2 and prove that your algorithm can fail on such an input. (d) Suppose that k = 2 and we can guarantee that neither local minimum is closer than n/3 positions to the middle of the array, and that the “joining point” of the two singly-raludominular subarrays lays in the middle third of the array. Now write an algorithm that returns the minimum element of A in sublinear time. Prove that your algorithm is correct, give a recurrence relation for its running time, and solve for its asymptotic behavior.
4. (15 pts extra credit) Asymptotic relations like O, Ω, and Θ represent relationships between functions, and these relationships are transitive. That is, if some f(n) = Ω(g(n)), and g(n) = Ω(h(n)), then it is also true that f(n) = Ω(h(n)). This means that we can sort functions by their asymptotic growth.1 Sort the following functions by order of asymptotic growth such that the final arrangement of functions g1,g2,...,g12 satisfies the ordering constraint g1 = Ω(g2), g2 = Ω(g3), ..., g11 = Ω(g12). n n1.5 8lgn 4lg∗ n n! (lgn)! 5 4n n1/lgn nlgn lg(n!) en 42
Give the final sorted list and identify which pair(s) functions f(n),g(n), if any, are in the same equivalence class, i.e., f(n) = Θ(g(n)).
1The notion of sorting is entirely general: so long as you can define a pairwise comparison operator for a set of objects S that is transitive, then you can sort the things in S. For instance, for strings, we use a comparison based on lexical ordering to sort them. Furthermore, we can use any sorting algorithm to sort S, by simply changing the comparison operators , <, etc. to have a meaning appropriate for S. For instance, using Ω, O, and Θ, you could apply QuickSort or MergeSort to the functions here to obtain the sorted list.