Description
1. Consider the proof of Lemma 4.3 of the Master Theorem provided in the course text, which proves that equation 4.23 is in O(nlogb a).
Expand on each step of the proof: to get from one line of your proof to the next, only a single property or log formula may be used and you should state which one you used. [5 marks]
2. Prove that lgn is not polynomially bounded from below, i.e. that lgn / ∈ Θ(nx) for anyx 0. Use this fact to show that the following recurrence relation cannot be solved using the master theorem as stated in the course text.[5 marks] T(n) =?4Tn 2?+ n2 lgn if n 1 Θ(1) if n = 1.
3. Solve the recurrence relation stated above using the guess-and-verify method.[5 marks]
4. For the proof of the median-of-median method, the input was divided into groups of five. Derive recurrence relations for two variations of this method: one that divides the input into groups of seven and one that divides the input into groups of three. Comment on whether the choice of group size has any effect on the asymptotic run time of the algoritm. [10 marks]
5. Using the recursion-tree method, solve the following recurrence relation, T(n) = 7T(n/2)+ n2, if n 1 and T(1) = 1. You may assume that n is an even power of 2. Show your work in detail and express your answer as a Θ bound on T(n). [5 marks]
1
6. Use a recursion-tree to establish a guess and then use the guess-and-verify method to solve the following recurrence: T(n) = T(n/2)+T(n/4)+T(n/8) if n 0 and T(1) = 1 for n = 1. You may assume n is an even power of 8. [10 marks]
7. Create an algorithm that sorts an array, A, of size n where each element is a distinct number. The array is approximately sorted, meaning that every element in A is at most k positions away from its position once A is sorted (for some constant k). For convenience, assume that n is an even power of 2. Derive the upper bound on the asymptotic runtime complexity of your algorithm. If possibly, sort this array in O(n) time. [20 marks]
8. You are in the process of developing a sorting algorithm that runs on a computer cluster with m nodes. You break your input (of size nm) into m equally sized arrays and send each one to a node for sorting. Then each node sends their results back to a single node for further processing.
(a) Devise an effecient algorithm for combining the results from each node into a single sorted array using a divide-and-conquer approach. Assume this algorithm uses only one node. Give a brief argument for the O bound, in terms of n and m, on the step that combines the m arrays into a single sorted array. [10 marks] (b) Now imagine you know of a data structure that given n elements has the following runtime complexities: • Finding the minimum element is Θ(1), • Deleting the minimum element is Θ(lgn), • Inserting an element is Θ(lgn). Use this data structure to create an algorithm with the same asymptotic upper bound as your divide-and-conquer algorithm. Again, assume this algorithm uses only one node. [10 marks] (c) Finally, comment on the conditions when the divide-and-conquer algorithm would be preferred and when the data structure approach would be preferred.[5 marks]
