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

### COMP 2080 Winter 2022 Assignment 5

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
``````
``````(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
``````