An N N matrix is monotone if each of its rows and columns are sorted in nondecreasing order. For example, 1 12 17 19 A= 15 18 20 25 16 23 26 30 24 27 31 35 is monotone. Given monotone matrix A and value a, the membership problem is to test whether a A or a & A. More specifically MEM(a,mi, N1, M2, 12) will return TRUE if there exist inj such that a = A[i, j] where my sism, and n, sin, and FALSE otherwise. (Note that we are using standard matrix notation here. The m's are the rows and the n's are the columns. The top row is 1 and the bottom one N, while the left column is 1 and the right column is N. Thus A[3, 2] = 23.) For example, in the given matrix, MEM(31,1,1, 4, 4) == TRUE while MEM(31,1,1,3,3) == FALSE. The next page gives pseudocode for MEM(a, m1, N1, M2, n2) (a) Prove that this algorithm (i) terminates and (ii) correctly solves the membership problem for monotone matrices. (b) Show that without monotonicity, the algorithm might not be correct. To do this, give an example of a 5 x 5 non-monotone matrix A and value a such that a E A but MEM(a,1,1,5, 5) would return false. (c) Analyze, from scratch (no use of other theorems allowed) the running time of the algorithm when run on an N * N monotone matrix, i.e., when MEM(a,1,1, N, N) is called. You may assume that N is always of the form N = 2 +1, k a non- negative integer, if that makes the analysis easier. The running time should measure the worst case number of comparisons made and be given using 00 notation. Your running time should be as precise as possible, e.g, if the running time is actually (N2) then O(Nlog N) would not be tight enough but O(N2) would be. % Check Validity of indices MEM(a,m, nu, m2, n2): If ((m > m2) OR (n > n2)) Return(FALSE) Else if (( m = m2) AND (n1 = n2)) { If (a = A[mu, na]) Return(TRUE) Else Return(FALSE) } % Check if only one element % Check if 2 x 1 submatrix Else if ((m +1=m2) AND (n = n2)) { If ((a = A[mi, n)) OR (a = A[m2, na])) Return(TRUE) Else Return(FALSE) } % Check if 1 x 2 submatrix Else if ((m = m2) AND (n1+1= n2)) { If ((a = A[m, n)) OR (a = A[m, n2])) Return(TRUE) Else Return(FALSE) } Else if ((m +1 = m2) AND (n +1 = n2)) % Check if 2 x 2 submatrix { If ((a = A[m2, n1)) OR (a = A[mi, n2]) OR (a = A[m2, n1)) OR (a = A[m2, n2])) Return(TRUE) Else Return(FALSE) } :U: 2 2 % Recurse on smaller matrices % lower-left submatrix % upper-right submatrix % upper-left submatrix Else { us If (Mem(a, u, ni, m2, v) = TRUE) Return(TRUE) If (Mem(a,m, v, u, n2) = TRUE)} Return(TRUE) If (a A[u, v]) If (Mem(a, u, v, m2, 12) = TRUE) Return(TRUE) Return(FALSE) } % lower-right submatrix An N N matrix is monotone if each of its rows and columns are sorted in nondecreasing order. For example, 1 12 17 19 A= 15 18 20 25 16 23 26 30 24 27 31 35 is monotone. Given monotone matrix A and value a, the membership problem is to test whether a A or a & A. More specifically MEM(a,mi, N1, M2, 12) will return TRUE if there exist inj such that a = A[i, j] where my sism, and n, sin, and FALSE otherwise. (Note that we are using standard matrix notation here. The m's are the rows and the n's are the columns. The top row is 1 and the bottom one N, while the left column is 1 and the right column is N. Thus A[3, 2] = 23.) For example, in the given matrix, MEM(31,1,1, 4, 4) == TRUE while MEM(31,1,1,3,3) == FALSE. The next page gives pseudocode for MEM(a, m1, N1, M2, n2) (a) Prove that this algorithm (i) terminates and (ii) correctly solves the membership problem for monotone matrices. (b) Show that without monotonicity, the algorithm might not be correct. To do this, give an example of a 5 x 5 non-monotone matrix A and value a such that a E A but MEM(a,1,1,5, 5) would return false. (c) Analyze, from scratch (no use of other theorems allowed) the running time of the algorithm when run on an N * N monotone matrix, i.e., when MEM(a,1,1, N, N) is called. You may assume that N is always of the form N = 2 +1, k a non- negative integer, if that makes the analysis easier. The running time should measure the worst case number of comparisons made and be given using 00 notation. Your running time should be as precise as possible, e.g, if the running time is actually (N2) then O(Nlog N) would not be tight enough but O(N2) would be. % Check Validity of indices MEM(a,m, nu, m2, n2): If ((m > m2) OR (n > n2)) Return(FALSE) Else if (( m = m2) AND (n1 = n2)) { If (a = A[mu, na]) Return(TRUE) Else Return(FALSE) } % Check if only one element % Check if 2 x 1 submatrix Else if ((m +1=m2) AND (n = n2)) { If ((a = A[mi, n)) OR (a = A[m2, na])) Return(TRUE) Else Return(FALSE) } % Check if 1 x 2 submatrix Else if ((m = m2) AND (n1+1= n2)) { If ((a = A[m, n)) OR (a = A[m, n2])) Return(TRUE) Else Return(FALSE) } Else if ((m +1 = m2) AND (n +1 = n2)) % Check if 2 x 2 submatrix { If ((a = A[m2, n1)) OR (a = A[mi, n2]) OR (a = A[m2, n1)) OR (a = A[m2, n2])) Return(TRUE) Else Return(FALSE) } :U: 2 2 % Recurse on smaller matrices % lower-left submatrix % upper-right submatrix % upper-left submatrix Else { us If (Mem(a, u, ni, m2, v) = TRUE) Return(TRUE) If (Mem(a,m, v, u, n2) = TRUE)} Return(TRUE) If (a A[u, v]) If (Mem(a, u, v, m2, 12) = TRUE) Return(TRUE) Return(FALSE) } % lower-right submatrix