算法代写 | 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


程序代写代做C/C++/JAVA/安卓/PYTHON/留学生/PHP/APP开发/MATLAB


blank

本网站支持淘宝 支付宝 微信支付  paypal等等交易。如果不放心可以用淘宝交易!

E-mail: itcsdx@outlook.com  微信:itcsdx


如果您使用手机请先保存二维码,微信识别。如果用电脑,直接掏出手机果断扫描。

blank

发表评论