[SOLVED] CS algorithm CSC240 Winter 2021 Homework Assignment 7

CSC240 Winter 2021 Homework Assignment 7
due Tuesday March 16, 2021
1. Consider the following algorithm that searches an m n array A[1..m, 1..n] of integers in which the entires of each row are sorted in nondecreasing order from left to right and the entries of each column are sorted in nondecreasing order from top to bottom.
SEARCH(A, m, n, x)
rowm
col1 while(row1)and(coln)do
if x = A[row, col] then return(true) if x < A[row, col]then row row 1else col col + 11 2 3 4 5 6 7 8formed by SEARCH(A, m, n, x).Prove matching upper and lower bounds on T. Do not use asymptotic notation.2. Consider the following recursive algorithm for computing the determinant of an n n matrix B[1..n, 1..n]:det(B, n)return(false)Let T(m,n) denote the worst case number of comparisons between x and entries in A per-1234567891011121314ifn=1thenreturnB[1,1] d0fork1tondofor i 1 to n 1 do if k > 1 then
for j 1 to k 1 do C[i, j] B[i + 1,j]
if k < n thenfor j k to n 1 doC[i, j] B[i + 1, j + 1] if k is eventhen d d B[1, k] det(C, n 1)else d d + B[1, k] det(C, n 1) return dLet M : Z+ N be the function such that M(n) is the number of multiplications performed by det(B, n) for any n n matrix B.Let A : Z+ N be the function such that A(n) is the number of assignments performed by det(B, n) for any n n matrix B.1(a) Give recursive definitions for M and A. Justify them by explaining how each part relates to the algorithm.(b) Provethatn!1M(n)2n!nforallnZ+.(c) Prove that M(n) A(n) for all n Z+.(d) Prove that there exist a constant u Z+ and a polynomial h(n) such that A(n) un! h(n) for all n Z+.2