Question 8: Let m 1 and n 1 be integers and consider an m n matrix A. The rows of this matrix are numbered 1,2...-, m, and its columns are numbered 1, 2, , n. 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 1. We say that the matrix A is awesome, if g(1) g(2) S g(3) s $ g(m) In the matrix below, the smallest number in each row is in boldface. For this example, we have m-4, n-10, g(1)3, g(2)3, g(3)-5, and g(4)-8. Thus, this matrix is 13 12 5 8 6 9 15 20 19 7 3 4 1 17 6 13 7 10 2 5 19 5 12 7 2 4 11 13 6 3 7 4 17 10 5 14 12 3 20 6 From now on, we assume that the m x n matrix A is awesome. Let i be an integer with 1 3 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).(2).. . g(m) in O(mn) total time. In the rest of this exercise, you will show that all values g(1),g(2)., g(m) can be computed in Om log 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 in O(m +n) total time. Assume thatm2, i.e., m is a power of two. Describe a recursive algorithm FINDMINIMA that has the following specification: Algorithm FINDMINIMA(A, i): Input: An m x n awesome matrix A and an integer i with 0 sisk Output: The values g (j-m/2) for J-1, 2, 3, . . . ,2i For each i with 0 s i K 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)(n) 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 9(1).9(2), . g(m) can be coinputed in O(m +n log m) total time Hint: 1+2+2+23 + +2t-2m. Question 8: Let m 1 and n 1 be integers and consider an m n matrix A. The rows of this matrix are numbered 1,2...-, m, and its columns are numbered 1, 2, , n. 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 1. We say that the matrix A is awesome, if g(1) g(2) S g(3) s $ g(m) In the matrix below, the smallest number in each row is in boldface. For this example, we have m-4, n-10, g(1)3, g(2)3, g(3)-5, and g(4)-8. Thus, this matrix is 13 12 5 8 6 9 15 20 19 7 3 4 1 17 6 13 7 10 2 5 19 5 12 7 2 4 11 13 6 3 7 4 17 10 5 14 12 3 20 6 From now on, we assume that the m x n matrix A is awesome. Let i be an integer with 1 3 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).(2).. . g(m) in O(mn) total time. In the rest of this exercise, you will show that all values g(1),g(2)., g(m) can be computed in Om log 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 in O(m +n) total time. Assume thatm2, i.e., m is a power of two. Describe a recursive algorithm FINDMINIMA that has the following specification: Algorithm FINDMINIMA(A, i): Input: An m x n awesome matrix A and an integer i with 0 sisk Output: The values g (j-m/2) for J-1, 2, 3, . . . ,2i For each i with 0 s i K 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)(n) 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 9(1).9(2), . g(m) can be coinputed in O(m +n log m) total time Hint: 1+2+2+23 + +2t-2m