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)
row←m
col←1 while(row≥1)and(col≤n)do
if x = A[row, col] then return(true) if x < A[row, col]
then row ← row − 1
else col ← col + 1
1 2 3 4 5 6 7 8
formed 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-
1
2
3
4
5
6
7
8
9
10
11
12
13
14
ifn=1thenreturnB[1,1] d←0
fork←1tondo
for 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 then
for j ← k to n − 1 do
C[i, j] ← B[i + 1, j + 1] if k is even
then d ← d − B[1, k]× det(C, n − 1)
else d ← d + B[1, k]× det(C, n − 1) return d
Let 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!−1≤M(n)≤2n!−nforalln∈Z+.
(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