算法代写 | CSC240 Winter 2021 Homework Assignment 7

本次cs代写的主要内容是递归算法的实现分析

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

  1. (a)  Give recursive definitions for M and A. Justify them by explaining how each part relates to the algorithm.
  2. (b)  Provethatn!−1≤M(n)≤2n!−nforalln∈Z+.
  3. (c)  Prove that M(n) ≤ A(n) for all n ∈ Z+.
  4. (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