assignment | 算法代写 | 数据结构代写 – COMP 2080 Winter 2022 Assignment 5

COMP 2080 Winter 2022 Assignment 5

assignment – , 该题目是值得借鉴的assignment代写的题目

ass代做 assignment代写 代写assignment

This assignment .

Proofs will be graded on both correctness and presentation. Clearly explain all of your steps.

Questions

  1. This question refers to the following recurrence relation.
T(n) =
{
4 , n= 1
3 T(n1) + 3n^1 , n > 1
(a) [3 marks]Use the substitution method to solve this recurrence relation.
(b)[3 marks]Prove that your solution from part (a) is correct using mathematical induction.
  1. This question refers to the following recurrence relation.
T(n) =
0 , n= 1
5
2 , n= 2
T(n2) + 2n, n > 2
(a) [4 marks]Use the substitution method to solve this recurrence relation. Consider the
case wherenis oddonly. You donotneed to repeat your calculation for the case where
nis even. Simplify your answer until no summation notation remains.
(b)[3 marks]The closed form solution to this recurrence relation is
T(n) =
(n1)(n+ 3)
2
, n 1.
Prove that this solution is correct using mathematical induction. Note that you do not
need to separate the case wherenis odd from the case wherenis even.
  1. This question refers to the following code. Assume that the/symbol represents integer division:a/b=
a
b
.
1 //pre: A.length >= 10 <= j,k < A.length
2 void myFnc(int[] A, int j, int k)
3 if (j < k-2)
4 nonsense(A, j, k)
5 myFnc(A, (3*j+k)/4 + 1, (j+k)/2)
6 myFnc(A, (j+k)/2 + 1, (j+3*k)/4)
1
Letn=kj+ 1. Assume thatnonsense(A, j, k)performs some operation on the entries
A[j],.. .,A[k]inclusive, and that if this function acts onnentries, its cost is
n.
(a) [3 marks]LetT(n) be the cost of myFnc()as a function of the input sizen. Find
the recurrence relation that definesT(n). You will need to use the floor and/or ceiling
functions. The only variable should ben: the indicesjandkshould not appear. (Caution:
how many base cases do you need?)
Use the simplified conventions for counting steps that were described and used in the
Week 6 notes. For example, a fixed number of steps that does not depend on the size
ofncan be approximated by 1. For any functionf(n) such thatf(n)(1), the sum
f(n) + 1 can be approximated byf(n).
For the remainder of this question, assume thatn= 4rfor somer0.
(b)[2 marks]In the special case wheren= 4r, show that your recurrence relation from part
(a) can be simplified to the following form.
T(n) =
{
c, nd
aT
(n
b
)
+f(n), n > d
(c) [4 marks]Draw the recursion tree for your recurrence relation from part (b). Include
enough rows to establish a pattern for the entries. Calculate the sum of each row, and
use the result to conjecture a functiong(n) so thatT(n)(g(n)).
(d)[2 marks]Explain which case of the Master Theorem applies to the recurrence relation
from part (b), and use that case to prove your conjecture from part (c).
  1. For each of the following recurrence relations, explain which case of the Master Theorem applies, then use the Master Theorem to find a functiong(n) such thatT(n)(g(n)).
(a) [2 marks]
T(n) =
{
1 , n 2
9 T
(n
5
)
+n^2 log(n), n > 2
(b)[2 marks]
T(n) =
{
1 , n= 1
4 T
(n
8
)
+ 3n^2 /^3 + log(n), n > 1
(c) [2 marks]
T(n) =
{
1 , n 3
17 T
(n
4
)
+n^2 +n^3 /^2 , n > 3
2