P2: (20 pts) Monotone Matrices An N * N matrix is monotone if each of its rows and columns are sorted in nondecreasing order. For example, A= 1 12 17 19 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 i, j such that a = A[i, j] where mi si m2 and ni m2) OR (n1 > 12) % Check Validity of indices Return(FALSE) Else if ((m = m2) AND (n1 = n2)) % Check if only one element { if (a = A[m1, 111]) Return (TRUE) Else Return(FALSE) } Else if ((m +1 = m2) AND (n1 = 112)) % Check if 2 x 1 submatrix { If ((a = A[m1, 711)) OR (a = A[m2, n1))) Return(TRUE) Else Return(FALSE) } Else if ((m = my) AND (n1 +1 = n2)) % Check if 1 x 2 submatrix { If (a = A[m1, 11)) 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[m1, ]) OR (a = A[mi, na)) OR (a = A[m2, ]) OR (a = A[m2, n2]) Return (TRUE) Else Return(FALSE) } m2 U= % Recurse on smaller matrices % lower-left submatrix % upper-right submatrix % upper-left submatrix Else { u If (Mem(a, u, N1, m2, v) = TRUE) Return(TRUE) If (Mem(a, m1, 0, 4, 12) = TRUE)} Return(TRUE) If (a A[u, u)) If (Mem(a, u, v, m2, na) = TRUE) Return(TRUE) Return(FALSE) } % lower-right submatrix