Recurrence relation assignmentCOMP 2080 Analysis of Algorithms Department of Computer Science...

Question

Recurrence			relation assignmentCOMP 2080 Analysis of Algorithms Department of Computer Science University of Manitoba COMP 2080 Winter 2023 – Assignment 5 This assignment is due by 11:59pm on Wednesday March 8. Submission instructions. Your assignment will be submitted in Crowdmark and not in UM Learn. A Crowdmark invitation will be sent to your U of M email. Proofs will be graded on both correctness and presentation. Clearly explain all of your steps. The total number of points is 30. Questions 1. This question refers to the following recurrence relation. T (n) = { 1, n = 0 2T (n− 1) + n, n ≥ 1 (a) [2 marks] Assume that n is much larger than 1. Use the recurrence relation to write T (n) in terms of T (n− 1), then in terms of T (n− 2), then in terms of T (n− 3). You can perform more substitutions if you wish in order to see the pattern. (b) [2 marks] Conjecture an expression for T (n) in terms of T (n − j), for an arbitrary j. Your expression can involve summation notation. For what range of j values does your conjecture apply? (c) [2 marks] Using part (b), conjecture a closed-form solution for T (n) as a function of n. Evaluate any summation notation. Here are two useful identities that hold for any n ≥ 1 and any constant q, q > 0 and q ̸= 1. n−1∑ k=0 qk = qn − 1 q − 1 , n−1∑ k=0 kqk = nqn + 1 q − 1 − q n+1 − 1 (q − 1)2 (d) [3 marks] Prove your conjecture using mathematical induction. 2. This question refers to the following recurrence relation. T (n) =  0, n = 0 9 8 , n = 1 T (n− 2) + n3, n ≥ 2 (a) In parts (i) – (iii), consider the case where n is even only. You do not need to repeat your calculation for the case where n is odd. 1 COMP 2080 Analysis of Algorithms Department of Computer Science University of Manitoba (i) [2 marks] Assume that n is much larger than 1. Use the recurrence relation to write T (n) in terms of T (n− 2), then in terms of T (n− 4), then in terms of T (n− 6). (ii) [2 marks] Conjecture an expression for T (n) in terms of T (n−2j), for an arbitrary j. For what range of j values does your conjecture apply? (iii) [2 marks] Using part (ii), conjecture a closed-form solution for T (n) as a function of n. Evaluate any summation notation. Hint: do not expand out a term like (n−2k)3. Instead, define a new index of summation that makes the summand simpler. (b) [3 marks] The closed form solution to this recurrence relation is T (n) = 1 8 n2(n+ 2)2, ∀n ≥ 0. Prove that this solution is correct using strong mathematical induction. Note that this formula holds for both even and odd n. Do not proceed by cases in the induction step. 3. This question refers to the following code. Assume that the / symbol represents integer division: a/b = ⌊ a b ⌋ . Let A be an integer array. 1 // pre: (A.length >= 1) ∧ (0  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 find a lower bound and an upper bound for the sum of all of the entries in the tree. Use that result to conjecture a function g(n) so that T (n) ∈ Θ(g(n)). You do not need to prove your conjecture. 4. [3 marks] For each of the following recurrence relations, explain which case of the Master Theorem applies, then use the Master Theorem to find a function g(n) such that T (n) ∈ Θ(g(n)). (a) T (n) = { 1, n ≤ 15 4T ( n 16 ) + 5n2/3, n > 15 (b) T (n) = { 1, n ≤ 2 30T ( n 3 ) + 4n3 − n, n > 2 (c) T (n) = { 1, n ≤ 5 6T ( n 6 ) + 15n, n > 5 3

Aditi · Accepted Answer

SOLUTION
1. 
(a) We can expand the recurrence relation for T(n) in terms of T(n-1) as follows:
T(n) = 2T(n-1) + n
= 2(2T(n-2) + n-1) + n
= 2^2 T(n-2) + 2n - 1
= 2^2(2T(n-3) + n-2) + 2n - 1
= 2^3 T(n-3) + 2^2n - 2^1 - n + 1
Continuing this process, we can write T(n) in terms of T(n-j) as:
T(n) = 2^j T(n-j) + 2^{j-1}n - 2^{j-2}(j-1) - ... - 2^1(j-(j-1)) - 2^0(j-j+1)
= 2^j T(n-j) + n2^{j-1} - 2^{j-1}j
(b) From the expression derived in part (a), we can see that T(n) can be expressed in terms of T(n-j) for any j, using the following expression:
T(n) = Σ_{k=0}^j 2^k(n-j+k)
This conjecture applies for any j value between 0 and n-1.
(c) Using the identity provided, we can evaluate the summation in the expression derived in part (b) as follows:
Σ_{k=0}^j 2^k(n-j+k) = 2^{j+1}(n-j) - 2j - 2
Substituting this expression into the formula for T(n) from part (b), we get:
T(n) = 2^j T(n-j) + 2^{j+1}(n-j) - 2j - 2^{j+1}
Using the identity provided again, we can simplify this expression to get a closed-form solution for T(n):
T(n) = 2^n - n - 2
(d) We can prove the conjecture using mathematical induction.
Base case: T(0) = 1 = 2^0 - 0 - 2
Inductive step: Assume T(k) = 2^k - k - 2 for all k between 0 and n-1.
We need to show that T(n) = 2^n - n - 2.
From part (a), we know that T(n) = 2T(n-1) + n. Substituting the inductive hypothesis, we get:
T(n) = 2(2^{n-1} - (n-1) - 2) + n
= 2^n - 2(n-1) - 4 + n
= 2^n - n - 2
This completes the induction and shows that the conjecture is true for all n.
2.
(a) (i) For even n, we have: T(n) = T(n-2) + n/3 Substituting n-2 for n, we have: T(n-2) = T(n-4) + (n-2)/3 Substituting this in the previous equation, we get: T(n) = T(n-4) + (n-2)/3 + n/3 T(n) = T(n-4) + (2n-2)/3 Substituting n-4 for n, we get: T(n-4) = T(n-6) + (n-4)/3 Substituting this in the previous equation, we get:

COMP 2080Analysis of AlgorithmsDepartment of Computer ScienceUniversity of ManitobaCOMP 2080 Winter 2023 – Assignment 5This assignment is due by 11:59pm on Wednesday March 8.Submission...

Answer To: COMP 2080Analysis of AlgorithmsDepartment of Computer ScienceUniversity of ManitobaCOMP 2080...

Answer To This Question Is Available To Download

Related Questions & Answers

Submit New Assignment