Question 8: Letm 1 and n1 be integers and consider an mxn matrix A. The rows of this matrix are numbered 1,2,... m, and its columns are numbered 1,2,.. Each entry of A stores one number and, for each row, all numbers in this row are pairwise distinct. For each i-: 1, 2, . . . , m, define g(i) the position (i.e., column number) of the smallest number in row i We say that the matrix A is awesome, if 9(1) S g(2) g(3) . g(m) In the matrix below, the smallest number in each row is in boldface. For this example, we have m-4, n 10, ) 3, g(2) 3, 9(3) 5, and g(4) 8. Thus, this matrix is awesome 13 12 5 8 6 9 15 20 19 7 3 4 1 17 6 13 7 10 2 5 19 5 12 72 4 11 13 6 3 7 4 17 10 5 14 12 3 20 6 From now on, we assume that the mx n matrix A is awesome. .Let i be an integer with 1 i m. Describe, in plain English and a few sentences, an algorithm that computes g(i) in O(n) time . Describe, in plain English and a few sentences, an algorithm that computes all values g(1),g(2)...g(n) in O(m) total time In the rest of this exercise, you will show that all values g(1),g(2).g(m) can be computed in O(m+nlog m) total time .Assume that m is even and assume that you are given the values Describe, in plain English and using one or more figures, an algorithm that computes the values g(1),g(3),9(5),9(7)g(m-1) in O(m +n) total time. .Assume that m 2*, i.e., m is a power of two. Describe a recursive algorithm FINDMINIMA that has the following specification: Algorithm FINDMINIMA(A, ): Input: An m n awesome matrix A and an integer i with 0 Output: The values g (j . m/2') for j = 1.2, 3, . 2' i k. For each i with0sis k, let T(i) denote the running time of algorithm FINDMINIMA(A, i) The running time of your algorithm must satisfy the recurrence T(0) T(i) -O(n). = T(i-1) + 0(2' + n), if I isk You may use plain English and figures to describe your algorithm, but it must be clear how you use recursion Assume again that m = 2k. Prove that all values g(1), g(2), . . . , g(m) can be computed in O(m +n log m) total time. Hint: 1+2+22+2++2 2m