COMP 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 co
ectness and presentation. Clearly explain all of your steps.
The total number of points is 30.
Questions
1. This question refers to the following recu
ence 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 recu
ence 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 a
itrary j.
Your expression can involve summation notation. For what range of j values does you
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 recu
ence 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 recu
ence 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 a
itrary
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 recu
ence relation is
T (n) =
1
8
n2(n+ 2)2, ∀n ≥ 0.
Prove that this solution is co
ect 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 intege
division: a
=
⌊
a
⌋
. Let A be an integer a
ay.
1
pre: (A.length >= 1) ∧ (0 <= j,k < A.length)
2 void recursiveFnc(int[] A, int j, int k)
3 if (j < k-6)
4 localFnc(A, j, k)
5 recursiveFnc(A, (7*j+k)/8 + 1, (5*j+3*k)/8)
6 recursiveFnc(A, (3*j+5*k)/8 + 1, (j+7*k)/8)
Let n = k− j +1. Assume that localFnc(A, j, k) performs some operation on the entries
A[j], . . ., A[k] inclusive, and that if this function acts on n entries, its cost is n3/2.
(a) [3 marks] Let T (n) be the cost of recursiveFnc() as a function of the input size n.
Find the recu
ence relation that defines T (n).
Use the simplified conventions for counting steps that were described and used in the
Week 7 notes. For example, a fixed number of steps that does not depend on the size
of n can be approximated by 1. A local cost function f(n) can be approximated by its
largest term.
You will need to use the floor and/or ceiling functions. The only variable should be n:
the indices j and k should not appear. Once you have eliminated j and k in favor of n,
you do not need to simplify your expressions any further.
For the remainder of Question 3, assume that n = 4r for some integer r ≥ 0.
2
COMP 2080
Analysis of Algorithms
Department of Computer Science
University of Manitoba
(b) [2 marks] In the special case where n = 4r for some integer r ≥ 0, show that you
ecu
ence relation from part (a) can be simplified to the following form.
T (n) =
{
c, n ≤ d
aT
(
n
)
+ f(n), n > d
(c) [4 marks] Draw the recursion tree for your recu
ence 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 recu
ence relations, explain which case of the Maste
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