Scribd
Upload
11 views

Tut-2_Solution

Uploaded by

arunachala.gaming
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
11 views

Tut-2_Solution

Uploaded by

arunachala.gaming
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 2

Birla Institute of Technology and Science-Pilani, Hyderabad Campus

Second Semester 2023-2024


Tutorial-2
Course No CS F364 Course Title: Design and Analysis of Algorithm
Date:24/1/24

General Instructions: Argue logically. Write it in a manner that explains your logic very
clearly. Do not miss steps in between.
Q1 Solve the recurrence relation of Tower of Hanoi problem using iterative method.
Q2 How many ones does the following procedure print when run with input n? Compute the best bounds
you can: the exact value if possible, a big-Θ expression if you can’t find the exact value, or big-O and
big-Ω bounds if you can’t find a big-Θ expression. [2022-23 Midsem]
Ones(n):
if n = 0 :
print 1
else:
for i = 1 to 2n :
Ones(n − 1)
Solution 2 The recurrence is T (n) = 2n T (n − 1), and T (0) = 1. Thus using iterative method the solution
n n(n+1)
will be T (n) = Πni=1 2i = 2Σi=1 i = 2 2 .
n(n+1) 2 2
Note that this quantitiy can be written as Θ(2 2 ) or 2Θ(n ) but not as Θ(2n ), since this last quantity
is roughly the square of the correct answer and is not bounded by a constant multiple of it.
Q3 Solve the following recurrence problems using substitution method.

1. T (n) = 2T (⌊ n2 ⌋ + 17) + n

Solution 3

1. We first guess the solution that T (n) ≤ cn log2 n.


Inductively, we will prove it.
n
T (n) = 2T (⌊ ⌋ + 17) + n
2
n n
≤ 2c(⌊ ⌋ + 17) log2 (⌊ ⌋ + 17) + n
2 2
n n
≤ 2c( + 17) log2 ( + 17) + n
2 2
n n n n
≤ 2c( + 17) log2 ( + ) + n [∀ ≥ 17i.e.n ≥ 68]
2 2 4 4
= (cn + 34c) log2 (3n/4) + n
= cn log2 n − cn log2 (4/3) + 34c log2 n − 34c log2 (4/3) + n
≤ cn log2 n − cn log2 (4/3) + 34c log2 n + n

As log2 n = O(n), we can say 34c log2 n ≤ kn ∀n ≥ n0 .


Thus
T (n) ≤ cn log2 n + n − cn log2 (4/3) + kn ∀n ≥ max{n0 , 68}
4
≤ cn log2 n + n(k + 1 − c log2 )
3
1
Let us choose c such that (k + 1 − c log2 34 ) ≤ 0 =⇒ (k + 1) ≤ c log2 4
3 ≤ c log2 4
2 =c
Thus T (n) ≤ cn log2 n for some constant c ≥ k + 1 and n ≥ max{n0 , 68}.

Q4 Solve the following recurrence to get the best asymptotic bounds you can on T (n) in each

1. T (n) = T ( 4 logn n ) + 2n for n > 1 and T (1) = 1. You can assume that all numbers are rounded down
2
to their nearest integer. You can use Master’s theorem. [2021-22 Midsem]

2. T (n) ≤ T (⌈ n2 ⌉) + T (⌊ n2 ⌋) + cn log n, for n ≥ 4 and T (2) = 2,(Do not use Master theorem here).
[2021-22 Midsem]

Solution 4

1. We will provide an upper and a lower bound to show that the best asymptotic bound for the
recurrence is Θ(n). A lower bound of Ω(n) follows from the 2n term in T (n).
n n
An upper bound can be reached by observing that 4 log n > 4 for n > 1, so T ( 4(log n) ) ≤ T ( 4 ) and
we have T (n) ≤ T ( n4 ) + 2n which, by Master’s theorem, is O(n). It follows that T (n) ∈ Θ(n).

2. We prove the by induction on n that T (n) ≤ cn log2 n = O(n log2 n)

(a) Base case: T (2) = 2 and 2 log2 2 = 2, done.


(b) Inductive hypothesis: Let k ≥ 2. Assume T (i) ≤ ci log2 i for all i ≤ k − 1.
(c) Inductive step: We prove the statement true for k.

T (k) ≤ T (⌈ k2 ⌉) + T (⌊ k2 ⌋) + ck log k
≤ c(⌈ k2 ⌉ log2 ⌈ k2 ⌉) + c(⌊ k2 ⌋ log2 ⌊ k2 ⌋) + ck log k
= ck(log2 ⌈ k2 ⌉) + ck log k
≤ ck log k log⌈ k2 ⌉ + ck log k
≤ ck log k(log k − 1) + ck log k
= ck log2 k

You might also like