Computer Engineering tment Kuwait University CpE-300 Design and Analysis of Algorithms Fall 2018-2019 Assignment 4 Instructor: Ameer Mohammed Due Date: 15/11/2018 Instructi You must submit your solutions to Schoology. Make your solutions as de- tailed as possible by clearly stating every step in your answer. Collaborations are allowed and encouraged However, you st independently write the solutions on your own and you must specify your collaborators (if any). Furthermore, you should cite your references whenever you use any external sources. Problems 1. (20 points) SELECT-7. Consider the deterministic selection algorithm SELECT that we saw in case where we divided the n elements into groups of 5, determined the pivot then recursively called SELECT on the appropriate sub-array. Suppose that we modified SELECT of that instead of dividing the n elements into groups of 5, we divided the elements into groups of 7. The rest of the procedure remains the same. Let us call this new algorithm SELECT-7 (a) (1 point) How many groups (in terms of n) will we have when divide the n elements into groups of 7? (b) (1 point) In each group, how many elements are greater than the group median? (c) (1 point) In each group, how many elements are less than the group median? (d) (1 point) How many elements (at least) are less than the pivot? (e) (1 point) How many elements (at least) are greater than the pivot? (f) (15 points) Write down and solve the recurrence of SELECT-7 using any method you prefer. Is the running time asymptotically better than the original SELECT algorithm? Explain your answer 2. (Bonus 10 points) Fast Median. You are given two sorted arrays A and B each contain- ing n distinct numbers. Describe an algorithm (using pseudocode) that runs in time (lg n) and finds the median of all the 2n elements that are contained in both A and B. (Hint think about how we recursively solved SELECT and try to do something similar here