questin 3 and 4

Define the median of a collection of N distinct comparable elements to be an element v from that collection that is larger than exactly [N/2] (or, equivalently, smaller than exactly [N/21-1) other elements from the same collection. Consider the problem of finding the median of the elements in two sorted lists of sizes m and n (not necessarily equal), respectively. point) 1. Express this problem formally (unique name, input conditions, output conditions). oints) 2. (a) Describe a simple algorithm to compute that median. (b) Find its tight (Big-Theta) asymptotically complexity as a function of the total number of elements. oints) 3. (a) Show how you can use the medians of the two lists to reduce an instance of this problem to smaller sub-instances. (b) State a precise self-reduction for this problem. oints) 4. (a) State a recursive algorithm that solves the problem based on your reduction. (b) For the special case when m= n, obtain from it a recurrence expressing its running time as a function of n. (c) Solve the recurrence and find a tight (Big-Theta) asymptotic bound on the complexity in the worst case. Define the median of a collection of N distinct comparable elements to be an element v from that collection that is larger than exactly [N/2] (or, equivalently, smaller than exactly [N/21-1) other elements from the same collection. Consider the problem of finding the median of the elements in two sorted lists of sizes m and n (not necessarily equal), respectively. point) 1. Express this problem formally (unique name, input conditions, output conditions). oints) 2. (a) Describe a simple algorithm to compute that median. (b) Find its tight (Big-Theta) asymptotically complexity as a function of the total number of elements. oints) 3. (a) Show how you can use the medians of the two lists to reduce an instance of this problem to smaller sub-instances. (b) State a precise self-reduction for this problem. oints) 4. (a) State a recursive algorithm that solves the problem based on your reduction. (b) For the special case when m= n, obtain from it a recurrence expressing its running time as a function of n. (c) Solve the recurrence and find a tight (Big-Theta) asymptotic bound on the complexity in the worst case