Recursion

Question 1

The recurrence relation capturing the optimal execution time of the Towers of Hanoi problem with n discs is

A
T(n) = 2T(n - 2) + 2
B
T(n) = 2T(n - 1) + n
C
T(n) = 2T(n/2) + 1
D
T(n) = 2T(n - 1) + 1
Question 1 Explanation: 
The recurrence equation for given recurrence function is
T(n) = 2T(n – 1) + 1
= 2 [2T(n – 2) + 1] + 1
= 22 T(n – 2) + 3

= 2k T( n – k) + (2k – 1)
n – k = 1
= 2n-1 T(1) + (2n-1 – 1)
= 2n-1 + 2n-1 – 1
= 2n – 1
≌ O(2n)
Question 2

The following recursive function in C is a solution to the Towers of Hanoi problem.

 Void move (int n, char A, char B, char C)
 {
     if (…………………………………) {
         move (…………………………………);
         printf(“Move disk %d from pole %c to pole %c\n”, n,A,C);
         move (………………………………….); 

Fill in the dotted parts of the solution.

A
Theory Explanation is given below.
Question 2 Explanation: 
move (disk-1, source, aux, dest) //Step-1
move disk from source to dest //Step-2
move (disk-1, aux, dest, source) //Step-3
Recurrence: 2T(n - 1) + 1
T(n) = 2T (n - 1) + 1
= 2[2T(n - 2) + 1] + 1
= 22T(n - 2) + 3

2k T(n - k) + (2k - 1)
= 2n-1T(1) + (2n-1 - 1)
= 2n-1 + 2n-1 - 1
= 2n - 1
≅ O(2n)
void move (int n, char A, char B, char C) {
if (n>0)
move(n-1, A, C, B);
printf("Move disk%d from pole%c to pole%c\n", n,A,C);
move(n-1, B, A, C);
}
}
Question 3

Consider the following recursive definition of fib:

 fib (n) : = if n = 0 then 1
             else if n = 1 than 1
             else fib (n – 1) + fib (n – 2)

The number of times fib is called (including the first call) for an evaluation of fib (7) is ___________

A
41
Question 3 Explanation: 
The recurrence relation for the no. of calls is
T(n) = T(n-1) + T(n-2) + 2
T(0) = T(1) = 0 (for fib(0) and fib(1), there are no extra recursive calls)
T(2) = 2
T(3) = 4
T(4) = 8
T(5) = 14
T(6) = 24
T(7) = 40
Counting the initial call, we get
40+1 = 41
There are 3 questions to complete.

Access quiz wise question and answers by becoming as a solutions adda PRO SUBSCRIBER with Ad-Free content

Register Now

If you have registered and made your payment please contact solutionsadda.in@gmail.com to get access