For simplicity, assume that n is a power of 2 (but, it is not needed in general). Suppose we are given a two dimensional integer array A[1 ...n, 1...n) in which every row is in nondecreasing order (from left to right) and also every column is in nondecreasing order (from top to bottom). Given such an A and an integer r, the problem is to determine if r is present in A. If r is present in A, the algorithm returns true; otherwise, it returns false. By comparing r to every entry in A, we can easily solve the problem in (n?) time. We want to design a better algorithm using divide and conquer (even faster algorithms than the ones proposed here are possible, but the homework is about divide and conquer). (1) Let T(n) be the complexity of your algorithm when the input array A has n rows and n columns. Consider A divided into four quadrants as shown below: A1 A2 A3 A4 Clearly, looking for r in A reduces to looking for r in each of A1, A2, Az, and A4 (each of which is a smaller and similar problem). Let us give names to these subproblems so that we can refer to them later: problem Aj: look for x in Aj problem A2: look for r in A2 problem Az: look for r in Az problem Aq: look for r in A4 (a) (5 pts) Suppose we solve all the four smaller problems (recursively, by dividing into 4 subproblems, until we find r or we are left with problems of size one, and those are the base cases). Do you think this approach will give an algorithm with better complexity than 0(n)? Justify your answer. There is no need to provide any algorithm. Read the following before attempting (b) through (e) Next, we want to consider the "middle" element of A and try to infer about the four smaller subproblems. Let mR= [1] and mC = [14], row and column indices respectively of the middle row" and "middle column". When you consider a (sub)problem where the indices of rows/columns involved are different, then you will cor- respondingly compute values of mR and mC. Consider A[ mR, mC], i.e., usual" middle element when we consider rows 1 through n and columns 1 through n (in general, the value at the bottom- right corner of the top-left quadrant of the part of the array in consideration). (b) (5 pts) Suppose A[mR, mC] 2. What can you infer about each of the four subproblems? Clearly identify the ones that do not have to solved anymore, and those that still have to be solved. Briefly justify. (d) (15 pts) Use your analysis from (b) and (c) to present complete pseu- docode for solving the problem of looking for r in A[i ... j, k ... l] using divide and conquer by specifying details of the following. Invoking the algorithm as search (A, 1, n, 1, n, x) solves the orig- inal problem. // Solves the problem of looking for x in Ai j, k ... l]) // Returns true if x is present in A[i ... j, k .. 1]; // returns false otherwise // Pre: (1) each of rows i through j is in nondecreasing order (left to right) (2) each of columns k through 1 is in nondecreasing order // (top to bottom) // (3) (j-i+1) (1-k+1), i.e., number of rows in the subproblem // = number of columns in the subproblem boolean search (A, i, j, k, l, x) { } You must clearly specify the base case(s). (e) (5 pts) Model T(n), the complexity of your algorithm when invoked as search (A, 1, n, 1, n, x), via a recurrence. Find a theta bound for T(n). Feel free to use the Master Theorem, if it can be used. For simplicity, assume that n is a power of 2 (but, it is not needed in general). Suppose we are given a two dimensional integer array A[1 ...n, 1...n) in which every row is in nondecreasing order (from left to right) and also every column is in nondecreasing order (from top to bottom). Given such an A and an integer r, the problem is to determine if r is present in A. If r is present in A, the algorithm returns true; otherwise, it returns false. By comparing r to every entry in A, we can easily solve the problem in (n?) time. We want to design a better algorithm using divide and conquer (even faster algorithms than the ones proposed here are possible, but the homework is about divide and conquer). (1) Let T(n) be the complexity of your algorithm when the input array A has n rows and n columns. Consider A divided into four quadrants as shown below: A1 A2 A3 A4 Clearly, looking for r in A reduces to looking for r in each of A1, A2, Az, and A4 (each of which is a smaller and similar problem). Let us give names to these subproblems so that we can refer to them later: problem Aj: look for x in Aj problem A2: look for r in A2 problem Az: look for r in Az problem Aq: look for r in A4 (a) (5 pts) Suppose we solve all the four smaller problems (recursively, by dividing into 4 subproblems, until we find r or we are left with problems of size one, and those are the base cases). Do you think this approach will give an algorithm with better complexity than 0(n)? Justify your answer. There is no need to provide any algorithm. Read the following before attempting (b) through (e) Next, we want to consider the "middle" element of A and try to infer about the four smaller subproblems. Let mR= [1] and mC = [14], row and column indices respectively of the middle row" and "middle column". When you consider a (sub)problem where the indices of rows/columns involved are different, then you will cor- respondingly compute values of mR and mC. Consider A[ mR, mC], i.e., usual" middle element when we consider rows 1 through n and columns 1 through n (in general, the value at the bottom- right corner of the top-left quadrant of the part of the array in consideration). (b) (5 pts) Suppose A[mR, mC] 2. What can you infer about each of the four subproblems? Clearly identify the ones that do not have to solved anymore, and those that still have to be solved. Briefly justify. (d) (15 pts) Use your analysis from (b) and (c) to present complete pseu- docode for solving the problem of looking for r in A[i ... j, k ... l] using divide and conquer by specifying details of the following. Invoking the algorithm as search (A, 1, n, 1, n, x) solves the orig- inal problem. // Solves the problem of looking for x in Ai j, k ... l]) // Returns true if x is present in A[i ... j, k .. 1]; // returns false otherwise // Pre: (1) each of rows i through j is in nondecreasing order (left to right) (2) each of columns k through 1 is in nondecreasing order // (top to bottom) // (3) (j-i+1) (1-k+1), i.e., number of rows in the subproblem // = number of columns in the subproblem boolean search (A, i, j, k, l, x) { } You must clearly specify the base case(s). (e) (5 pts) Model T(n), the complexity of your algorithm when invoked as search (A, 1, n, 1, n, x), via a recurrence. Find a theta bound for T(n). Feel free to use the Master Theorem, if it can be used