# Recursion in Data Structure MCQ

1. Recursion is a method in which the solution of a problem depends on ____________

a) Larger instances of different problems
b) Larger instances of the same problem
c) Smaller instances of the same problem
d) Smaller instances of different problems

Recursion is a programming technique using a function or algorithm that calls itself one or more times until a specified condition is met at which time the rest of each repetition is processed from the last one called to the first.

In recursion, the solution of a problem depends on the solution of smaller instances of the same problem.

2. Which of the following problems can’t be solved using recursion?

a) Factorial of a number
b) Nth fibonacci number
c) Length of a string
d) Problems without base case

Problems without a base case lead to infinite recursion calls. In general, we will assume a base case to avoid infinite recursion calls. Problems like finding the Factorial of a number, Nth Fibonacci number, and Length of a string can be solved using recursion.

3. Recursion is similar to which of the following?

a) Switch Case
b) Loop
c) If-else
d) if elif else

Recursion is similar to a loop. Most programming languages implement recursion by allowing a function to call itself. Recursive loops are also known simply as recursion.

4. In recursion, the condition for which the function will stop calling itself is ____________

a) Best case
b) Worst case
c) Base case
d) There is no such condition

In recursion, the condition for which the function will stop calling itself is Base case.

For recursion to end at some point, there always has to be a condition for which the function will not call itself. This condition is known as the base case.

8. How many times is the recursive function called, when the following code is executed?

void my_recursive_function(int n)
{
if(n == 0)
return;
printf("%d ",n);
my_recursive_function(n-1);
}
int main()
{
my_recursive_function(10);
return 0;
}

a) 9
b) 10
c) 11
d) 12

In this code, the recursive function is called 11 times.

9. What does the following recursive code do?

void my_recursive_function(int n)
{
if(n == 0)
return;
my_recursive_function(n-1);
printf("%d ",n);
}
int main()
{
my_recursive_function(10);
return 0;
}

a) Prints the numbers from 10 to 1
b) Prints the numbers from 10 to 0
c) Prints the numbers from 1 to 10
d) Prints the numbers from 0 to 10

The above code prints the numbers from 1 to 10.

10. Which of the following statements is true about recursion?

a) Recursion is always better than iteration
b) Recursion uses more memory compared to iteration
c) Recursion uses less memory compared to iteration
d) Iteration is always better and simpler than recursion

Recursion uses more memory compared to iteration because every time the recursive function is called, the function call is stored in the stack.

1. In general, which of the following methods isn’t used to find the factorial of a number?

a) Recursion
b) Iteration
c) Dynamic programming
d) Non iterative / recursive

In general, we use recursion, iteration, and dynamic programming to find the factorial of a number. We can also implement without using the iterative/recursive method by using tgammal() method. Most of us never use it generally.

2. Which of the following recursive formula can be used to find the factorial of a number?

a) fact(n) = n * fact(n)
b) fact(n) = n * fact(n+1)
c) fact(n) = n * fact(n-1)
d) fact(n) = n * fact(1)

The recursive formula can be used to find the factorial of a number is

fact(n) = n * fact(n – 1)

4. Consider the following recursive implementation to find the factorial of a number. Which of the lines should be inserted to complete the below code?

int fact(int n)
{
if(_________)
return 1;
return n * fact(n - 1);
}
int main()
{
int n = 5;
int ans = fact(n);
printf("%d",ans);
return 0;
}

a) n = 0
b) n != 0
c) n == 0
d) n == 1

The line “n == 0” should be inserted to complete the above code.

Note: “n == 1” cannot be used because it does not take care of the case when n = 0, i.e when we want to find the factorial of 0.

5. The time complexity of the following recursive implementation to find the factorial of a number is ________

int fact(int n)
{
if(_________)
return 1;
return n * fact(n - 1);
}
int main()
{
int n = 5;
int ans = fact(n);
printf("%d",ans);
return 0;
}

a) O(1)
b) O(n)
c) O(n2)
d) O(n3)

The time complexity of the above recursive implementation to find the factorial of a number is O(n).

6. What is the space complexity of the following recursive implementation to find the factorial of a number?

int fact(int n)
{
if(_________)
return 1;
return n * fact(n - 1);
}
int main()
{
int n = 5;
int ans = fact(n);
printf("%d",ans);
return 0;
}

a) O(1)
b) O(n)
c) O(n2)
d) O(n3)

The space complexity of the above recursive implementation to find the factorial of a number is O(1).

1. Suppose the first Fibonacci number is 0 and the second is 1. What is the sixth Fibonacci number?

a) 5
b) 6
c) 7
d) 8

If the first Fibonacci number is 0 and the second is 1. Then the sixth Fibonacci number is 5.

2. Which of the following is not a Fibonacci number?

a) 8
b) 21
c) 55
d) 14

14 is NOT a Fibonacci number because the sum of the last equation is larger than the number 14 and the sum of the equation before it is smaller than the number 14.

3. Which of the following option is wrong about the Fibonacci number?

a) Fibonacci number can be calculated by using Dynamic programming
b) Fibonacci number can be calculated by using the Recursion method
c) Fibonacci number can be calculated by using the Iteration method
d) No method is defined to calculate the Fibonacci number

The Fibonacci number can be calculated by using Dynamic Programming, the Recursion method, and Iteration Method.

3. Consider the following iterative implementation to find the nth Fibonacci number?

int main()
{
int n = 10,i;
if(n == 1)
printf("0");
else if(n == 2)
printf("1");
else
{
int a = 0, b = 1, c;
for(i = 3; i <= n; i++)
{
c = a + b;
________;
________;
}
printf("%d",c);
}
return 0;
}

Which of the following lines should be added to complete the above code?

a) c = b
b = a

b) a = b
b = c

c) b = c
a = b

d) a = b
b = a

The lines “a = b” and “b = c” should be added to complete the above code.

5. Which of the following recurrence relations can be used to find the nth Fibonacci number?

a) F(n) = F(n) + F(n – 1)
b) F(n) = F(n) + F(n + 1)
c) F(n) = F(n – 1)
d) F(n) = F(n – 1) + F(n – 2)

The relation F(n) = F(n – 1) + F(n – 2) can be used to find the nth fibonacci number.

6. Consider the following recursive implementation to find the nth Fibonacci number:

int fibo(int n)
{
if(n == 1)
return 0;
else if(n == 2)
return 1;
return ________;
}
int main()
{
int n = 5;
int ans = fibo(n);
printf("%d",ans);
return 0;
}

Which of the following lines should be inserted to complete the above code?

a) fibo(n – 1)
b) fibo(n – 1) + fibo(n – 2)
c) fibo(n) + fibo(n – 1)
d) fibo(n – 2) + fibo(n – 1)

The line fibo(n – 1) + fibo(n – 2) should be inserted to complete the above code.

7. Consider the following recursive implementation to find the nth fibonnaci number:

int fibo(int n)
{
if(n == 1)
return 0;
else if(n == 2)
return 1;
return fibo(n - 1) + fibo(n - 2);
}
int main()
{
int n = 5;
int ans = fibo(n);
printf("%d",ans);
return 0;
}

Which of the following is the base case?

a) if(n == 1)
b) else if(n == 2)
c) return fibo(n – 1) + fibo(n – 2)
d) both if(n == 1) and else if(n == 2)

Both if(n == 1) and else if(n == 2) are the base cases.

8. What is the time complexity of the following recursive implementation to find the nth Fibonacci number?

int fibo(int n)
{
if(n == 1)
return 0;
else if(n == 2)
return 1;
return fibo(n - 1) + fibo(n - 2);
}
int main()
{
int n = 5;
int ans = fibo(n);
printf("%d",ans);
return 0;
}

a) O(1)
b) O(2*n)
c) O(n2)
d) O(2n)

The time complexity of the above recursive implementation to find the nth Fibonacci number is O(2n).

1. Which of the following option is wrong about natural numbers?

a) Sum of first n natural numbers can be calculated by using the Iteration method
b) Sum of first n natural numbers can be calculated by using the Recursion method
c) Sum of first n natural numbers can be calculated by using the Binomial coefficient method
d) No method is prescribed to calculate the sum of the first n natural number

The methods used to find the sum of first n natural numbers are

a) Sum of first n natural numbers can be calculated by using the Iteration method
b) Sum of first n natural numbers can be calculated by using the Recursion method
c) Sum of first n natural numbers can be calculated by using the Binomial coefficient method

All of the above-mentioned methods can be used to find the sum of first n natural numbers.

2. Which of the following gives the sum of the first n natural numbers?

a) nC2
b) (n-1)C2
c) (n+1)C2
d) (n+2)C2

The sum of the first n natural numbers is given by n*(n+1)/2, which is equal to (n+1)C2.

3. Consider the following iterative solution to find the sum of the first n natural numbers:

#include
int get_sum(int n)
{
int sm = 0, i;
for(i = 1; i <= n; i++)
________;
return sm;
}
int main()
{
int n = 10;
int ans = get_sum(n);
printf("%d",ans);
return 0;
}

Which of the following lines completes the above code?

a) sm = i
b) sm += i
c) i = sm
d) i += sm

The line “sm += i” completes the above code.

9. Which of the following methods used to find the sum of first n natural numbers has the least time complexity?

a) Recursion
b) Iteration
c) Binomial coefficient
d) All have equal time complexity

Recursion and iteration take O(n) time to find the sum of first n natural numbers while binomial coefficient takes O(1) time.

1. Which of the following is not another name for GCD(Greatest Common Divisor)?

a) LCM
b) GCM
c) GCF
d) HCF

LCM (Least Common Multiple) and GCD are not the same. GCM (Greatest Common Measure), GCF (Greatest Common Factor), and HCF (Highest Common Factor) are other names for GCD.

2. What is the GCD of 8 and 12?

a) 8
b) 12
c) 2
d) 4

GCD is the largest positive integer that divides each of the integers. So the GCD of 8 and 12 is 4.

3. If the GCD of two numbers is 8 and LCM is 144, then what is the second number if the first number is 72?

a) 24
b) 2
c) 3
d) 16

If the GCD of two numbers is 8 and LCM is 144, then second number is 16 if the first number is 72

As A * B = GCD (A, B) * LCM (A, B).

So B = (144 * 8)/72 = 16.

4. Which of the following is also known as GCD?

a) Highest Common Divisor
b) Highest Common Multiple
c) Highest Common Measure
d) Lowest Common Multiple

GCM (Greatest Common Measure), GCF (Greatest Common Factor), HCF (Highest Common Factor), and HCF (Highest Common Divisor) are also known as GCD.

5. Which of the following is the coprime number?

a) 54 and 24
b) 4 and 8
c) 6 and 12
d) 9 and 28

Coprime numbers have GCD 1. So 9 and 28 are coprime numbers. While 54 and 24 have GCD 6, 4 and 8 have GCD 4, 6 and 12 have GCD 6.

6. In terms of the Venn Diagram, which of the following expression gives GCD (Given A ꓵ B ≠ Ø)?

a) Multiplication of A U B terms
b) Multiplication of A ꓵ B terms
c) Multiplication of A*B terms
d) Multiplication of A-B terms

In terms of the Venn Diagram, the GCD is given by the intersection of two sets. So A ꓵ B gives the GCD. While A U B gives the LCM.

7. What is the GCD according to the given Venn Diagram?

a) 2
b) 3
c) 5
d) 6

In terms of the Venn Diagram, the GCD is given by the intersection of two sets. So A ꓵ B gives the GCD. While A U B gives the LCM. So here A ꓵ B is 5.

8. What is the GCD of a and b?

a) a + b
b) gcd (a-b, b) if a>b
c) gcd (a+b, a-b)
d) a – b

As per Euclid’s Algorithm, gcd (a, b) = gcd (a-b, b) if a > b or gcd (a, b) = gcd (a, b-a) if b > a.

9. What is the GCD of 48, 18, 0?

a) 24
b) 2
c) 3
d) 6

GCD is the largest positive integer that divides each of the integers. So the GCD of 48, 18, 0 is 6.

10. Is 9 and 28 coprime number?

a) True
b) False

Coprime numbers have GCD 1. So 9 and 28 are coprime numbers.

11. If gcd (a, b) is defined by the expression, d=a*p + b*q where d, p, q are positive integers and a, b is both not zero, then what is the expression called?

a) Bezout’s Identity
b) Multiplicative Identity
c) Sum of Product
d) Product of Sum

If gcd (a, b) is defined by the expression

d=a*p + b*q

where d, p, q are positive integers
a, b is both not zero

Then the expression is called Bezout’s Identity, and p, q can be calculated by the extended form of the Euclidean algorithm.

12. Is gcd an associative function.

a) True
b) False

The gcd function is an associative function as gcd (a, gcd (b, c)) = gcd (gcd (a, b), c).

13. Which is the correct term of the given relation, gcd (a, b) * lcm (a, b) =?

a) |a*b|
b) a + b
c) a – b
d) a / b

The gcd is closely related to lcm as gcd (a, b) * lcm (a, b) = |a*b|.

14. Who gave the expression for the probability and expected value of gcd?

a) James E. Nymann
b) Riemann
c) Thomae
d) Euler

In the year 1972, James E. Nymann showed some results to show the probability and expected value of gcd.

15. What is the computational complexity of the Binary GCD algorithm where a and b are integers?

a) O (log a + log b)2
b) O (log (a + b))
c) O (log ab)
d) O (log a-b)

From the Binary GCD algorithm, it is found that the computational complexity is O (log a + log b)2 as the total number of steps in the execution is at most the total sum of a number of bits of a and b.

1. LCM is also called as ________

a) GCD
b) SCM
c) GCF
d) HCF

GCD (Greatest Common Divisor), GCF (Greatest Common Factor), and HCF (Highest Common Factor) is not an alias for LCM. LCM is also called Smallest Common Multiple(SCM).

2. What is the LCM of 8 and 13?

a) 8
b) 12
c) 20
d) 104

104 is the smallest positive integer that is divisible by both 8 and 12.

3. Which is the smallest number of 3 digits that is divisible by 2, 4, 8?

a) 100
b) 102
c) 116
d) 104

LCM of 2, 4, and 8 is 8. So check for the number that is divisible by 8. So 104 is the smallest number that is divisible by 2, 4, and 8.

4. Which of the following is also known as LCM?

a) Lowest Common Divisor
b) Least Common Multiple
c) Lowest Common Measure
d) Highest Common Multiple

The least Common Multiple is also known as LCM or Lowest Common Multiple.

5. What is the LCM of two coprime numbers?

a) 1
b) 0
c) Addition of two coprime numbers
d) Multiplication of two coprime numbers

Coprime numbers have GCD 1. While LCM of coprime numbers is the product of those two coprime numbers.

6. In terms of the Venn Diagram, which of the following expression gives LCM (Given A ꓵ B ≠ Ø)?

a) Multiplication of A U B terms
b) Multiplication of A ꓵ B terms
c) Multiplication of A*B terms
d) Multiplication of A-B terms

In terms of the Venn Diagram, the LCM is given by the Union of two sets. So A U B gives the LCM. While A ꓵ B gives the GCD.

7. What is the LCM according to the given Venn Diagram?

a) 2
b) 3
c) 180
d) 6

In terms of the Venn Diagram, the LCM is given by the Union of two sets. So A U B gives the LCM. So the product of all the terms is 180.

8. What is the lcm (a, b)?

a) a + b
b) gcd (a-b, b) if a>b
c) lcm (b, a)
d) a – b

Since the LCM function is commutative, so lcm (a, b) = lcm (b, a).

9. What is the LCM of 48, 18, 6?

a) 122
b) 12*2
c) 3
d) 6

The LCM of 48, 18, 6 is 144 and 122 is 144.

10. Is 9 and 28 coprime numbers.

a) True
b) False

Coprime numbers have GCD 1 and LCM is the product of the two given terms. So 9 and 28 are coprime numbers.

11. What is the following expression, lcm (an lcm (b, c) equal to?

a) lcm (a, b, c)
b) a*b*c
c) a + b + c
d) lcm (lcm (a, b), c)

Since LCM function follows associativity, hence lcm (a, lcm (b, c) is equal to lcm (lcm (a, b), c).

12. Is lcm an associative function.

a) True
b) False

The lcm function is an associative function as lcm (a, lcm (b, c) is equal to lcm (lcm (a, b), c).

13. Which is the correct term of the given relation, lcm (a, b) * gcd (a, b) =?

a) |a*b|
b) a + b
c) a – b
d) a / b

The lcm is closely related to gcd as lcm (a, b) * gcd (a, b) = |a*b|.

14. What is the following expression, lcm (a gcd (a, b)) equal to?

a) a
b) b
c) a*b
d) a + b

Since the lcm function follows absorption laws so lcm (a, gcd (a, b)) equal to a.

15. Which algorithm is the most efficient numerical algorithm to obtain lcm?

a) Euler’s Algorithm
b) Euclid’s Algorithm
c) Chebyshev Function
d) Partial Division Algorithm

The most efficient way of calculating the lcm of a given number is using Euclid’s algorithm which computes the lcm in much lesser time compared to other algorithms.

1. Which of the following methods can be used to find the sum of digits of a number?

a) Recursion
b) Iteration
c) Greedy algorithm
d) Both recursion and iteration

Both recursion and iteration can be used to find the sum of digits of a number.

2. What can be the maximum sum of digits for a 4-digit number?

a) 1
b) 16
c) 36
d) 26

The sum of digits will be maximum when all the digits are 9. Thus, the sum will be maximum for the number 9999, which is 36.

3. What can be the minimum sum of digits for a 4-digit number?

a) 0
b) 1
c) 16
d) 36

The sum of digits will be minimum for the number 1000 and the sum is 1.

9. How many times is the function recursive_sum_of_digits() called when the following code is executed?

#include
int recursive_sum_of_digits(int n)
{
if(n == 0)
return 0;
return n % 10 + recursive_sum_of_digits(n/10);
}
int main()
{
int n = 1201;
int ans = recursive_sum_of_digits(n);
printf("%d",ans);
return 0;
}

a) 6
b) 7
c) 5
d) 9

The function recursive_sum_of_digits() is called 8 times, when the following code is executed.

10. You have to find the sum of digits of a number given that the number is always greater than 0. Which of the following base cases can replace the base case for the below code?

#include
int recursive_sum_of_digits(int n)
{
if(n == 0)
return 0;
return n % 10 + recursive_sum_of_digits(n/10);
}
int main()
{
int n = 1201;
int ans = recursive_sum_of_digits(n);
printf("%d",ans);
return 0;
}

a) if(n == 0) return 1
b) if(n == 1) return 0
c) if(n == 1) return 1
d) no need to modify the base case

None of the above mentioned base cases can replace the base case if(n == 0) return 0.

3. What is the time complexity of the above code used to reverse a string?

a) O(1)
b) O(n)
c) O(n2)
d) O(n3)

The time complexity of the above code used to reverse a string is O(n).

1. Consider the following iterative implementation used to reverse a string:

#include
#include
void reverse_string(char *s)
{
int len = strlen(s);
int i,j;
i=0;
j=len-1;
while(______)
{
char tmp = s[i];
s[i] = s[j];
s[j] = tmp;
i++;
j--;
}
}

Which of the following lines should be inserted to complete the above code?

a) i > j
b) i < len
c) j > 0
d) i < j

The line “i < j” should be inserted to complete the above code.

2. What is the output of the following code?

#include
#include
void reverse_string(char *s)
{
int len = strlen(s);
int i,j;
i=0;
j=len-1;
while(i < j)
{
char tmp = s[i];
s[i] = s[j];
s[j] = tmp;
i++;
j--;
}
}
int main()
{
char s[100] = "reverse";
reverse_string(s);
printf("%s",s);
return 0;
}

a) ersevre
b) esrever
c) eserver
d) eresevr

The program reverses the string “reverse” and prints “esrever”.

3. What is the time complexity of the above code used to reverse a string?

a) O(1)
b) O(n)
c) O(n2)
d) O(n3)

The time complexity of the above code used to reverse a string is O(n).

4. What does the following code do?

#include
#include
void reverse_string(char *s)
{
int len = strlen(s);
int i,j;
i=0;
j=len-1;
while(i < j)
{
char tmp = s[i];
s[i] = s[j];
s[j] = tmp;
i++;
j--;
}
}
int main()
{
char s[100] = "abcdefg";
char t[100];
strcpy(t,s);
reverse_string(s);
if(strcmp(t,s) == 0)
printf("Yes");
else
printf("No");
return 0;
}

a) Copies a string to another string
b) Compares two strings
c) Reverses a string
d) Checks if a string is a palindrome

The main purpose of the above code is to check if a string is a palindrome.

5. What is the output of the following code?

#include
#include
void reverse_string(char *s)
{
int len = strlen(s);
int i,j;
i=0;
j=len-1;
while(i < j)
{
char tmp = s[i];
s[i] = s[j];
s[j] = tmp;
i++;
j--;
}
}
int main()
{
char s[100] = "rotator";
char t[100];
strcpy(t,s);
reverse_string(s);
if(strcmp(t,s) == 0)
printf("Yes");
else
printf("No");
return 0;
}

a) Yes
b) No
c) Runtime error
d) Compile time error

The program checks if a string is a palindrome. Since the string rotator is a palindrome, it prints “yes”.

6. Consider the following recursive implementation used to reverse a string:

void recursive_reverse_string(char *s, int left, int right)
{
if(left < right)
{
char tmp = s[left];
s[left] = s[right];
s[right] = tmp;
_________;
}
}

Which of the following lines should be inserted to complete the above code?

a) recursive_reverse_string(s, left+1, right+1)
b) recursive_reverse_string(s, left-1, right-1)
c) recursive_reverse_string(s, left+1, right-1)
d) recursive_reverse_string(s, left-1, right+1)

The line “recursive_reverse_string(s, left+1, right-1)” should be inserted to complete the above code.

7. What is the output of the following code?

#include
#include
void recursive_reverse_string(char *s, int left, int right)
{
if(left < right)
{
char tmp = s[left];
s[left] = s[right];
s[right] = tmp;
recursive_reverse_string(s, left+1, right-1);
}
}
int main()
{
char s[100] = "recursion";
int len = strlen(s);
recursive_reverse_string(s,0,len-1);
printf("%s",s);
return 0;
}

a) recursion
b) nsoirucer
c) noisrcuer
d) noisrucer

The program prints the reversed string of “recursion”, which is “noisrucer”.

8. How many times is the function recursive_reverse_string() called when the following code is executed?

#include
#include
void recursive_reverse_string(char *s, int left, int right)
{
if(left < right)
{
char tmp = s[left];
s[left] = s[right];
s[right] = tmp;
recursive_reverse_string(s, left+1, right-1);
}
}
int main()
{
int len = strlen(s);
recursive_reverse_string(s,0,len-1);
printf("%s",s);
return 0;
}

a) 3
b) 4
c) 5
d) 6

The function recursive_reverse_string() is called 3 times when the above code is executed.

9. What is the time complexity of the above recursive implementation used to reverse a string?

a) O(1)
b) O(n)
c) O(n2)
d) O(n3)

The time complexity of the above recursive implementation used to reverse a string is O(n).

10. In which of the following cases is the reversal of a string not equal to the original string?

a) Palindromic strings
b) Strings of length 1
c) Empty String
d) Strings of length 2

String “ab” is a string of length 2 whose reversal is not the same as the given one. Palindromic Strings, String of length 1, and Empty Strings case – the reversal is the same as the one given.

1. Which of the following is the binary representation of 100?

a) 1010010
b) 1110000
c) 1100100
d) 1010101

The binary representation of 100 is

100 = 64 + 32 + 4 = 26 + 25 + 22 = 1100100.

2. Consider the following iterative code used to convert a decimal number to its equivalent binary:

#include
void dec_to_bin(int n)
{
int arr[31],len = 0,i;
if(n == 0)
{
arr[0] = 0;
len = 1;
}
while(n != 0)
{
arr[len++] = n % 2;
_______;
}
for(i=len-1; i>=0; i--)
printf("%d",arr[i]);
}
int main()
{
int n = 10;
dec_to_bin(n);
return 0;
}

Which of the following lines should be inserted to complete the above code?

a) n–
b) n /= 2
c) n /= 10
d) n++

The line “n /= 2” should be inserted to complete the above code.

3. What is the output of the following code?

#include
void dec_to_bin(int n)
{
int arr[31],len = 0,i;
if(n == 0)
{
arr[0] = 0;
len = 1;
}
while(n != 0)
{
arr[len++] = n % 2;
n /= 2;
}
for(i=len-1; i>=0; i--)
printf("%d",arr[i]);
}
int main()
{
int n = 63;
dec_to_bin(n);
return 0;
}

a) 111111
b) 111011
c) 101101
d) 101010

The program prints the binary equivalent of 63, which is 111111.

4. What is the output of the following code?

#include
void dec_to_bin(int n)
{
int arr[31],len = 0,i;
if(n == 0)
{
arr[0] = 0;
len = 1;
}
while(n != 0)
{
arr[len++] = n % 2;
n /= 2;
}
for(i=len-1; i>=0; i--)
printf("%d",arr[i]);
}
int main()
{
int n = 0;
dec_to_bin(n);
return 0;
}

a) 0
b) 1
c) Runtime error
d) Garbage value

The program prints the binary equivalent of 0, which is 0.

5. What is the time complexity of the following code used to convert a decimal number to its binary equivalent?

#include
void dec_to_bin(int n)
{
int arr[31],len = 0,i;
if(n == 0)
{
arr[0] = 0;
len = 1;
}
while(n != 0)
{
arr[len++] = n % 2;
n /= 2;
}
for(i=len-1; i>=0; i--)
printf("%d",arr[i]);
}
int main()
{
int n = 0;
dec_to_bin(n);
return 0;
}

a) O(1)
b) O(n)
c) O(n2)
d) O(logn)

The time complexity of the above code used to convert a decimal number to its binary equivalent is O(long).

6. Consider the following recursive implementation used to convert a decimal number to its binary equivalent:

#include
int arr[31], len = 0;
void recursive_dec_to_bin(int n)
{
if(n == 0 && len == 0)
{
arr[len++] = 0;
return;
}
if(n == 0)
return;
__________;
recursive_dec_to_bin(n/2);
}
int main()
{
int n = 100,i;
recursive_dec_to_bin(n);
for(i=len-1; i>=0; i--)
printf("%d",arr[i]);
return 0;
}

Which of the following lines should be inserted to complete the above code?

a) arr[len] = n
b) arr[len] = n % 2
c) arr[len++] = n % 2
d) arr[len++] = n

The line “arr[len++] = n % 2” should be inserted to complete the above code.

7. Consider the following code:

#include
int arr[31], len = 0;
void recursive_dec_to_bin(int n)
{
if(n == 0 && len == 0)
{
arr[len++] = 0;
return;
}
if(n == 0)
return;
arr[len++] = n % 2;
recursive_dec_to_bin(n/2);
}

Which of the following lines is the base case for the above code?

a) if(n ==0 && len == 0)
b) if(n == 0)
c) if(n ==0 && len == 0) and if(n == 0)
d) if(n == 1)

Both of the above-mentioned lines are the base cases for the above code.

8. What is the output of the following code?

#include
int arr[31], len = 0;
void recursive_dec_to_bin(int n)
{
if(n == 0 && len == 0)
{
arr[len++] = 0;
return;
}
if(n == 0)
return;
arr[len++] = n % 2;
recursive_dec_to_bin(n/2);
}
int main()
{
int n = -100,i;
recursive_dec_to_bin(n);
for(i=len-1; i>=0; i--)
printf("%d",arr[i]);
return 0;
}

a) -1100100
b) 1100100
c) 2’s complement of 1100100
d) Garbage value

The program doesn’t handle negative inputs and so produces a garbage value.

9. What is the time complexity of the recursive implementation used to convert a decimal number to its binary equivalent?

#include
int arr[31], len = 0;
void recursive_dec_to_bin(int n)
{
if(n == 0 && len == 0)
{
arr[len++] = 0;
return;
}
if(n == 0)
return;
arr[len++] = n % 2;
recursive_dec_to_bin(n/2);
}

a) O(1)
b) O(n)
c) O(n2)
d) O(logn)

The time complexity of the recursive implementation used to convert a decimal number to its binary equivalent is O(long).

10. What is the space complexity of the recursive implementation used to convert a decimal number to its binary equivalent?

#include
int arr[31], len = 0;
void recursive_dec_to_bin(int n)
{
if(n == 0 && len == 0)
{
arr[len++] = 0;
return;
}
if(n == 0)
return;
arr[len++] = n % 2;
recursive_dec_to_bin(n/2);
}

a) O(1)
b) O(n)
c) O(n2)
d) O(logn)

The space complexity of the recursive implementation used to convert a decimal number to its binary equivalent is O(long).

11. What is the output of the following code?

#include
int arr[31], len = 0;
void recursive_dec_to_bin(int n)
{
if(n == 0 && len == 0)
{
arr[len++] = 0;
return;
}
if(n == 0)
return;
arr[len++] = n % 2;
recursive_dec_to_bin(n/2);
}
int main()
{
int n = 111,i;
recursive_dec_to_bin(n);
for(i=len-1; i>=0; i--)
printf("%d",arr[i]);
return 0;
}

a) 1110111
b) 1001111
c) 1101111
d) 1010111

The program prints the binary equivalent of 111, which is 1101111.

12. How many times is the function recursive_dec_to_bin() called when the following code is executed?

#include
int arr[31], len = 0;
void recursive_dec_to_bin(int n)
{
if(n == 0 && len == 0)
{
arr[len++] = 0;
return;
}
if(n == 0)
return;
arr[len++] = n % 2;
recursive_dec_to_bin(n/2);
}
int main()
{
int n = 111,i;
recursive_dec_to_bin(n);
for(i=len-1; i>=0; i--)
printf("%d",arr[i]);
return 0;
}

a) 7
b) 8
c) 9
d) 10

The function recursive_dec_to_bin() is called 8 times when the above code is executed.

1. Consider the following iterative implementation used to find the length of a linked list:

struct Node
{
int val;
struct Node *next;
int get_len()
{
int len = 0;
while(_____)
{
len++;
temp = temp->next;
}
return len;
}

Which of the following conditions should be checked to complete the above code?

a) temp->next != 0
b) temp == 0
c) temp != 0
d) temp->next == 0

The condition “temp != 0” should be checked to complete the above code.

2. What is the output of the following code?

#include
#include
struct Node
{
int val;
struct Node *next;
int get_len()
{
int len = 0;
while(temp != 0)
{
len++;
temp = temp->next;
}
return len;
}
int main()
{
int arr[10] = {1,2,3,4,5}, n = 5, i;
struct Node *temp, *newNode;
for(i=0; i<n; i++)
{
newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->val = arr[i];
newNode->next = 0;
temp->next = newNode;
temp = temp->next;
}
int len = get_len();
printf("%d",len);
return 0;
}

a) 4
b) 5
c) 6
d) 7

The program prints the length of the linked list, which is 5.

3. What is the time complexity of the following iterative implementation used to find the length of a linked list?

#include
#include
struct Node
{
int val;
struct Node *next;
int get_len()
{
int len = 0;
while(temp != 0)
{
len++;
temp = temp->next;
}
return len;
}
int main()
{
int arr[10] = {1,2,3,4,5}, n = 5, i;
struct Node *temp, *newNode;
for(i=0; i<n; i++)
{
newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->val = arr[i];
newNode->next = 0;
temp->next = newNode;
temp = temp->next;
}
int len = get_len();
printf("%d",len);
return 0;
}

a) O(1)
b) O(n)
c) O(n2)
d) O(logn)

The time complexity of the above iterative implementation used to find the length of a linked list is O(n).

4. What is the output of the following code?

#include
#include
struct Node
{
int val;
struct Node *next;
int get_len()
{
int len = 0;
while(temp != 0)
{
len++;
temp = temp->next;
}
return len;
}
int main()
{
int arr[10] = {1,2,3,4,5}, n = 5, i;
struct Node *temp, *newNode;
int len = get_len();
printf("%d",len);
return 0;
}

a) 0
b) Garbage value
c) Compile time error
d) Runtime error

The program prints the length of the linked list, which is 0.

5. Which of the following can be the base case for the recursive implementation used to find the length of the linked list?

#include
#include
struct Node
{
int val;
struct Node *next;
int get_len()
{
int len = 0;
while(temp != 0)
{
len++;
temp = temp->next;
}
return len;
}
int main()
{
int arr[10] = {1,2,3,4,5}, n = 5, i;
struct Node *temp, *newNode;
int len = get_len();
printf("%d",len);
return 0;
}

a) if(current_node == 0) return 1
b) if(current_node->next == 0) return 1
c) if(current_node->next == 0) return 0
d) if(current_node == 0) return 0

The line “if(current_node == 0) return 0” can be used as a base case in the recursive implementation used to find the length of a linked list.

Note: The line “if(current_node->next == 0) return 1” cannot be used because it won’t work when the length of the linked list is zero.

6. Which of the following lines should be inserted to complete the following recursive implementation used to find the length of a linked list?

#include
#include
struct Node
{
int val;
struct Node *next;
int recursive_get_len(struct Node *current_node)
{
if(current_node == 0)
return 0;
return _____;
}
int main()
{
int arr[10] = {1,2,3,4,5}, n = 5, i;
struct Node *temp, *newNode;
for(i=0; i<n; i++)
{
newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->val = arr[i];
newNode->next = 0;
temp->next = newNode;
temp = temp->next;
}
printf("%d",len);
return 0;
}

a) recursive_get_len(current_node)
b) 1 + recursive_get_len(current_node)
c) recursive_get_len(current_node->next)
d) 1 + recursive_get_len(current_node->next)

The line “1 + recursive_get_len(current_node->next)” should be inserted to complete the above code.

7. What is the output of the following code?

#include
#include
struct Node
{
int val;
struct Node *next;
int recursive_get_len(struct Node *current_node)
{
if(current_node == 0)
return 0;
return 1 + recursive_get_len(current_node->next);
}
int main()
{
int arr[10] = {-1,2,3,-3,4,5,0}, n = 7, i;
struct Node *temp, *newNode;
for(i=0; i<n; i++)
{
newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->val = arr[i];
newNode->next = 0;
temp->next = newNode;
temp = temp->next;
}
printf("%d",len);
return 0;
}

a) 6
b) 7
c) 8
d) 9

The program prints the length of the linked list, which is 7.

8. What is the time complexity of the following code used to find the length of a linked list?

#include
#include
struct Node
{
int val;
struct Node *next;
int recursive_get_len(struct Node *current_node)
{
if(current_node == 0)
return 0;
return 1 + recursive_get_len(current_node->next);
}
int main()
{
int arr[10] = {-1,2,3,-3,4,5,0}, n = 7, i;
struct Node *temp, *newNode;
for(i=0; i<n; i++)
{
newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->val = arr[i];
newNode->next = 0;
temp->next = newNode;
temp = temp->next;
}
printf("%d",len);
return 0;
}

a) O(1)
b) O(n)
c) O(n2)
d) O(n3)

To find the length of the linked list, the program iterates over the linked list once. So, the time complexity of the above code is O(n).

9. What is the output of the following code?

#include
#include
struct Node
{
int val;
struct Node *next;
int recursive_get_len(struct Node *current_node)
{
if(current_node == 0)
return 0;
return 1 + recursive_get_len(current_node->next);
}
int main()
{
int arr[10] = {-1,2,3,-3,4,5}, n = 6, i;
struct Node *temp, *newNode;
for(i=0; i<n; i++)
{
newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->val = arr[i];
newNode->next = 0;
temp->next = newNode;
temp = temp->next;
}
printf("%d",len);
return 0;
}

a) 5
b) 6
c) 7
d) 8

The program prints the length of the linked list, which is 6.

10. How many times is the function recursive_get_len() called when the following code is executed?

#include
#include
struct Node
{
int val;
struct Node *next;
int recursive_get_len(struct Node *current_node)
{
if(current_node == 0)
return 0;
return 1 + recursive_get_len(current_node->next);
}
int main()
{
int arr[10] = {-1,2,3,-3,4,5}, n = 6, i;
struct Node *temp, *newNode;
for(i=0; i<n; i++)
{
newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->val = arr[i];
newNode->next = 0;
temp->next = newNode;
temp = temp->next;
}
printf("%d",len);
return 0;
}

a) 5
b) 6
c) 7
d) 8

The function is called “len + 1” times. Since the length of the linked list in the above code is 6, the function is called 6 + 1 = 7 times.

1. If Matrix A is of order X*Y and Matrix B is of order M*N, then what is the order of Matrix A*B given that Y=M?

a) Y*N
b) X*M
c) X*N
d) Y*M

The Matrix A*B is of order X*N as it is given that Y=M i.e. number of columns in Matrix A is equal to the total number of rows in matrix B. So the Matrix A*B must have X number of rows and N number of columns.

2. How many recursive calls are there in Recursive matrix multiplication through the Simple Divide and Conquer Method?

a) 2
b) 6
c) 9
d) 8

For the multiplication of two square matrices recursively using the Simple Divide and Conquer Method, there are 8 recursive calls performed for high time complexity.

3. What is the time complexity of the matrix multiplied recursively by the Divide and Conquer Method?

a) O(n)
b) O(n2)
c) O(n3)
d) O(n!)

The time complexity of recursive multiplication of two square matrices by the Divide and Conquer method is found to be O(n3) since there is a total of 8 recursive calls.

4. What is the time complexity of matrix multiplied recursively by Strassen’s Method?

a) O(nlog7)
b) O(n2)
c) O(n3)
d) O(n!)

The time complexity of recursive multiplication of two square matrices by Strassen’s Method is found to be O(nlog7) since there are a total of 7 recursive calls.

5. How many recursive calls are there in Recursive matrix multiplication by Strassen’s Method?

a) 5
b) 7
c) 8
d) 4

For the multiplication of two square matrices recursively using Strassen’s Method, there are 7 recursive calls performed for high time complexity.

6. Matrix A is of order 3*4 and Matrix B is of order 4*5. How many elements will be there in a matrix A*B multiplied recursively?

a) 12
b) 15
c) 16
d) 20

The resultant matrix will be of order 3*5 when multiplied recursively and therefore the matrix will have 3*5=15 elements.

7. If Matrix X is of order A*B and Matrix Y is of order C*D, and B=C then the order of Matrix X*Y is A*D?

a) True
b) False

Given that B=C, so the two matrices can be recursively multiplied. Therefore, the order of the Matrix X*Y is A*D.

8. What is the time complexity of the fastest known matrix multiplication algorithm?

a) O(nlog7)
b) O(n2.37)
c) O(n3)
d) O(n!)

The Coppersmith-Winograd algorithm multiplies the matrices in O(n2.37) time. Several improvements have been made in the algorithm since 2010.

9. Is the Coppersmith-Winograd algorithm better than Strassen’s algorithm in terms of time complexity?

a) True
b) False

The Coppersmith-Winograd algorithm multiplies the matrices in O(n2.37) time. The time complexity of recursive multiplication of two square matrices by Strassen’s Method is found to be O(n2.80).

Therefore, the Coppersmith-Winograd algorithm is better than Strassen’s algorithm in terms of time complexity.

1. Which of the following statement is true about the stack?

a) Pop operation removes the top most element
b) Pop operation removes the bottom-most element
c) Push operation adds a new element at the bottom
d) Push operation removes the top most element

As the stack is based on LIFO(Last In First Out) principle so the deletion takes place from the topmost element. Thus pop operator removes the topmost element.

2. What is the space complexity of the program to reverse stack recursively?

a) O(1)
b) O(log n)
c) O(n)
d) O(n log n)

The recursive program to reverse stack uses the memory of the order n to store the function call stack. The space complexity of the program to reverse stack recursively is O(n).

3. Stack can be reversed without using extra space by _____________

a) using recursion
b) using a linked list to implement stack
c) using an extra stack
d) it is not possible

If a linked list is used for implementing the stack then it can be reversed without using any extra space.

4. Which of the following is considered as the top of the stack in the linked list implementation of the stack?

a) the Last node
b) the First node
c) Random node
d) Middle node

The first node is considered the top element when the stack is implemented using a linked list.

5. What is the time complexity of the program to reverse stack when a linked list is used for its implementation?

a) O(n)
b) O(n log n)
c) O(n2)
d) O(log n)

As a linked list takes O(n) time for getting reversed thus linked list version of the stack will also take the same time.

6. Which of the following takes O(n) time in the worst case in array implementation of the stack?

a) pop
b) push
c) isEmpty
d) pop, push, and isEmpty takes constant time

Functions pop, push, and isEmpty all are implemented in constant time in the worst case.

7. What will be the time complexity of the code to reverse stack recursively?

a) O(n)
b) O(n log n)
c) O(log n)
d) O(n2)

The recurrence relation for the recursive code to reverse stack will be given by T (n)=T(n-1)+n. This is calculated to be equal to O(n2).

1. Which of the following sorting algorithm has the best case time complexity of O(n2)?

a) bubble sort
b) selection sort
c) insertion sort
d) stupid sort

Selection sort is not an adaptive sorting algorithm. It finds the index of the minimum element in each iteration even if the given array is already sorted. Thus its best-case time complexity becomes O(n2).

2. Which of the following is the biggest advantage of selection sort?

a) it has low time complexity
b) it has low space complexity
c) it is easy to implement
d) it requires only n swaps under any condition

Selection sort works by obtaining the least value element in each iteration and then swapping it with the current index. So it will take n swaps under any condition which will be useful when a memory write operation is expensive.

3. What will be the recurrence relation of the code of recursive selection sort?

a) T(n) = 2T(n/2) + n
b) T(n) = 2T(n/2) + c
c) T(n) = T(n-1) + n
d) T(n) = T(n-1) + c

Function to find the minimum element index takes n time. The recursive call is made to one less element than in the previous call so the overall recurrence relation becomes T(n) = T(n-1) + n.

4. Which of the following sorting algorithm is NOT stable?

a) Selection sort
b) Brick sort
c) Bubble sort
d) Merge sort

Out of the given options selection sort is the only algorithm that is not stable. It is because the order of identical elements in sorted output may be different from the input array.

5. What will be the best case time complexity of recursive selection sort?

a) O(n)
b) O(n2)
c) O(log n)
d) O(n log n)

The selection sort’s algorithm is such that it finds the index of the minimum element in each iteration even if the given array is already sorted. Thus its best-case time complexity becomes O(n2).

6. Recursive selection sort is a comparison-based sort.

a) true
b) false

In the selection sort, we need to compare elements in order to find the minimum element in each iteration. So we can say that it uses comparisons in order to sort the array. Thus it qualifies as a comparison-based sort.

7. What is the average case time complexity of recursive selection sort?

a) O(n)
b) O(n log n)
c) O(n2)
d) O(log n)

The overall recurrence relation of recursive selection sort is given by T(n) = T(n-1) + n. It is found to be equal to O(n2). It is unvaried throughout the three cases.

8. What is the bidirectional variant of selection sort?

a) cocktail sort
b) BOGO sort
c) gnome sort
d) bubble sort

A bidirectional variant of selection sort is called cocktail sort. It’s an algorithm that finds both the minimum and maximum values in the array in every pass. This reduces the number of scans of the array by a factor of 2.

10. What is the number of swaps required to sort the array arr={5,3,2,4,1} using recursive selection sort?

a) 0
b) 1
c) 2
d) 3

The first swap takes place between 1 and 5. The second swap takes place between 3 and 2 which sorts our array.

1. Which of the following methods can be used to find the largest and smallest element in an array?

a) Recursion
b) Iteration
c) Both recursion and iteration
d) No method is suitable

Both recursion and iteration can be used to find the largest and smallest element in an array.

2. Consider the following iterative code snippet to find the largest element:

int get_max_element(int *arr,int n)
{
int i, max_element = arr[0];
for(i = 1; i < n; i++)
if(________)
max_element = arr[i];
return max_element;
}

Which of the following lines should be inserted to complete the above code?

a) arr[i] > max_element
b) arr[i] < max_element
c) arr[i] == max_element
d) arr[i] != max_element

The line “arr[i] > max_element” should be inserted to complete the above code snippet.

3. Consider the following code snippet to find the smallest element in an array:

int get_min_element(int *arr, int n)
{
int i, min_element = arr[0];
for(i = 1; i < n; i++)
if(_______)
min_element = arr[i];
return min_element;
}

Which of the following lines should be inserted to complete the above code?

a) arr[i] > min_element
b) arr[i] < min_element
c) arr[i] == min_element
d) arr[i] != min_element

The line “arr[i] < min_element” should be inserted to complete the above code.

6. What is the time complexity of the following iterative implementation used to find the largest and smallest element in an array?

#include
int get_max_element(int *arr,int n)
{
int i, max_element = arr[0];
for(i = 1; i < n; i++)
if(arr[i] > max_element)
max_element = arr[i];
return max_element;
}
int get_min_element(int *arr, int n)
{
int i, min_element;
for(i = 1; i < n; i++)
if(arr[i] < min_element)
min_element = arr[i];
return min_element;
}
int main()
{
int n = 7, arr[7] = {1,1,1,0,-1,-1,-1};
int max_element = get_max_element(arr,n);
int min_element = get_min_element(arr,n);
printf("%d %d",max_element,min_element);
return 0;
}

a) O(1)
b) O(n)
c) O(n2)
d) O(n/2)

The time complexity of the above iterative implementation used to find the largest and the smallest element in an array is O(n).

10. How many times is the function recursive_min_element() called when the following code is executed?

int min_of_two(int a, int b)
{
if(a < b)
return a;
return b;
}
int recursive_min_element(int *arr, int len, int idx)
{
if(idx == len - 1)
return arr[idx];
return min_of_two(arr[idx], recursive_min_element(arr, len, idx + 1));
}
int main()
{
int n = 10, idx = 0, arr[] = {5,2,6,7,8,9,3,-1,1,10};
int min_element = recursive_min_element(arr,n,idx);
printf("%d",min_element);
return 0;
}

a) 9
b) 10
c) 11
d) 12

The function recursive_min_element() is called 10 times when the above code is executed.

1. Which of the following methods can be used to find the largest and smallest number in a linked list?

a) Recursion
b) Iteration
c) Both Recursion and iteration
d) Impossible to find the largest and smallest numbers

Both recursion and iteration can be used to find the largest and smallest number in a linked list.

1. Which of the following techniques can be used to search an element in an unsorted array?

a) Iterative linear search
b) Recursive binary search
c) Iterative binary search
d) Normal binary search

Iterative linear search can be used to search an element in an unsorted array.
Note: Binary search can be used only when the array is sorted.

2. Consider the array {1,1,1,1,1}. Select the wrong option?

a) Iterative linear search can be used to search for the elements in the given array
b) Recursive linear search can be used to search for the elements in the given array
c) Recursive binary search can be used to search for the elements in the given array
d) No method is defined to search for an element in the given array

Iterative linear search, Recursive linear search, and Recursive binary search can be applied to search for an element in the above-given array.

8. How many times is the function recursive_search_num() called when the following code is executed?

#include
int recursive_search_num(int *arr, int num, int idx, int len)
{
if(idx == len)
return -1;
if(arr[idx] == num)
return idx;
return recursive_search_num(arr, num, idx+1, len);
}
int main()
{
int arr[8] ={1,2,3,3,3,5,6,7},num=5,len = 8;
int indx = recursive_search_num(arr,num,0,len);
printf("Index of %d is %d",num,indx);
return 0;
}

a) 5
b) 6
c) 7
d) 8

The function recursive_search_num() is called 6 times when the above code is executed.

6. What is the time complexity of the above recursive implementation of binary search?

a) O(n)
b) O(2n)
c) O(logn)
d) O(n!)

The time complexity of the above recursive implementation of binary search is O(long).

1. Which of the following methods can be used to search an element in a linked list?

a) Iterative linear search
b) Iterative binary search
c) Recursive binary search
d) Normal binary search

Iterative linear search can be used to search an element in a linked list. Binary search can be used only when the list is sorted.

7. Can binary search be applied on a sorted linked list in O(Logn) time?

a) No
b) Yes

Since the linked list doesn’t allow random access, binary search cannot be applied on a sorted linked list in O(Logn) time.

8. What will be the time complexity when a binary search is applied on a linked list?

a) O(1)
b) O(n)
c) O(n2)
d) O(n3)

The time complexity will be O(n) when a binary search is applied on a linked list.

4. Recursive program to raise an integer x to power y uses which of the following algorithm?

a) Dynamic programming
b) Backtracking
c) Divide and conquer
d) Greedy algorithm

The recursive approach uses the divide and conquers algorithm as we break the problem into smaller parts and then solve the smaller parts and finally combine their results to get the overall solution.

5. What is the least time in which we can raise a number x to power y?

a) O(x)
b) O(y)
c) O(log x)
d) O(log y)

We can optimize the code for finding the power of a number by calculating x raised to power y/2 only once and using it depending on whether y is even or odd.

7. What is the advantage of iterative code for finding the power of number over recursive code?

a) Iterative code requires less time
b) Iterative code requires less space
c) Iterative code is more compiler friendly

Both iterative and recursive approaches can be implemented in log n time but the recursive code requires memory in the call stack which makes it less preferable.

9. Recursive approach to finding the power of a number is preferred over the iterative approach.

a) True
b) False

The recursive code requires memory in the call stack which makes it less preferable as compared to the iterative approach.

1. What is the objective of the tower of Hanoi puzzle?

a) To move all disks to some other rod by following rules
b) To divide the disks equally among the three rods by following rules
c) To move all disks to some other rod in random order
d) To divide the disks equally among three rods in random order

The objective of the tower of Hanoi problem is to move all disks to some other rod by following the following rules-

1) Only one disk can be moved at a time.

2) Disk can only be moved if it is the uppermost disk of the stack.

3) No disk should be placed over a smaller disk.

2. Which of the following is NOT a rule of the tower of Hanoi puzzle?

a) No disk should be placed over a smaller disk
b) Disk can only be moved if it is the uppermost disk of the stack
c) No disk should be placed over a larger disk
d) Only one disk can be moved at a time

The rule of the Hanoi puzzle is to not put a disk over a smaller one. Putting a smaller disk over a larger one is allowed.

3. The time complexity of the solution tower of the Hanoi problem using recursion is _________

a) O(n2)
b) O(2n)
c) O(n log n)
d) O(n)

The time complexity of the problem can be found out by solving the recurrence relation: T(n)=2T(n-1)+c. The result of trelationshiption is found to be equal to 2n. It can be solved using substitution.

4. Recurrence equation formed for the tower of hanoi problem is given by _________

a) T(n) = 2T(n-1)+n
b) T(n) = 2T(n/2)+c
c) T(n) = 2T(n-1)+c
d) T(n) = 2T(n/2)+n

As there are 2 recursive calls to n-1 disks and one constant time operation so the recurrence relation will be given by T(n) = 2T(n-1)+c.

5. Minimum number of moves required to solve a Tower of Hanoi problem with n disks is __________

a) 2n
b) 2n-1
c) n2
d) n2-1

A minimum number of moves can be calculated by solving the recurrence relation – T(n)=2T(n-1)+c.

Alternatively, we can observe the pattern formed by the series of a number of moves 1,3,7,15…..Either way, it turns out to be equal to 2n-1.

6. Space complexity of recursive solution of the Tower of Hanoi puzzle is ________

a) O(1)
b) O(n)
c) O(log n)
d) O(n log n)

The space complexity of the tower of Hanoi problem can be found out by solving the recurrence relation T(n)=T(n-1)+c.

The result of this relation is found out to be n. It can be solved using substitution.

8. Recursive solution of the Tower of Hanoi problem is an example of which of the following algorithm?

a) Dynamic programming
b) Backtracking
c) Greedy algorithm
d) Divide and conquer

The recursive approach uses the divide and conquers algorithm as we break the problem into smaller parts and then solve the smaller parts and finally combine their results to get the overall solution.

9. Tower of Hanoi problem can be solved iteratively.

a) True
b) False

An iterative solution to the tower of Hanoi puzzle also exists. Its approach depends on whether the total numbers of disks are even or odd.

10. Minimum time required to solve the Tower of Hanoi puzzle with 4 disks assuming one move takes 2 seconds, will be __________

a) 15 seconds
b) 30 seconds
c) 16 seconds
d) 32 seconds

Number of moves = 24-1=16-1=15
Time for 1 move = 2 seconds
Time for 15 moves = 15×2 = 30 seconds.

1. Master’s theorem is used for?

a) solving recurrences
b) solving iterative relations
c) analyzing loops
d) calculating the time complexity of any code

Master’s theorem is a direct method for solving recurrences. We can solve any recurrence that falls under any one of the three cases of the master’s theorem.

2. How many cases are there under Master’s theorem?

a) 2
b) 3
c) 4
d) 5

There are primarily 3 cases under the master’s theorem. We can solve any recurrence that falls under any one of these three cases.

3. What is the result of the recurrences which fall under first case of Master’s theorem (let the recurrence be given by T(n)=aT(n/b)+f(n) and f(n)=nc?

a) T(n) = O(n^logba)
b) T(n) = O(nc log n)
c) T(n) = O(f(n))
d) T(n) = O(n2)

In the first case of the master’s theorem, the necessary condition is that c < logba. If this condition is true then T(n) = O(n^logba).

4. What is the result of the recurrences which fall under second case of Master’s theorem (let the recurrence be given by T(n)=aT(n/b)+f(n) and f(n)=nc?

a) T(n) = O(nlogba)
b) T(n) = O(nc log n)
c) T(n) = O(f(n))
d) T(n) = O(n2)

In second case of the master’s theorem the necessary condition is that c = logba. If this condition is true then T(n) = O(nc log n)

5. What is the result of the recurrences which fall under third case of Master’s theorem (let the recurrence be given by T(n)=aT(n/b)+f(n) and f(n)=nc?

a) T(n) = O(nlogba)
b) T(n) = O(nc log n)
c) T(n) = O(f(n))
d) T(n) = O(n2)

In third case of master’s theorem the necessary condition is that c > logba. If this condition is true then T(n) = O(f(n)).

6. We can solve any recurrence by using the Master’s theorem.

a) true
b) false

No we cannot solve all the recurrences by only using the master’s theorem. We can solve only those which fall under the three cases prescribed in the theorem.

7. Under what case of Master’s theorem will the recurrence relation of merge sort fall?

a) 1
b) 2
c) 3
d) It cannot be solved using the master’s theorem

The recurrence relation of merge sort is given by T(n) = 2T(n/2) + O(n). So we can observe that c = Logba so it will fall under case 2 of master’s theorem.

8. Under what case of Master’s theorem will the recurrence relation of stooge sort fall?

a) 1
b) 2
c) 3
d) It cannot be solved using the master’s theorem

The recurrence relation of stooge sort is given as T(n) = 3T(2/3n) + O(1). It is found to be equal to O(n2.7) using the master’s theorem first case.

9. Which case of master’s theorem can be extended further?

a) 1
b) 2
c) 3
d) No case can be extended

The second case of the master’s theorem can be extended for a case

where

f(n) = nc (log n)k and the resulting recurrence becomes T(n)= O(nc (log n))k+1.

10. What is the result of the recurrences which fall under the extended second case of Master’s theorem (let the recurrence be given by T(n)=aT(n/b)+f(n) and f(n)=nc(log n)k?

a) T(n) = O(nlogba)
b) T(n) = O(nc log n)
c) T(n)= O(nc (log n)k+1
d) T(n) = O(n2)

In the extended second case of the master’s theorem, the necessary condition is that c = logba. If this condition is true then T(n)= O(nc(log n))k+1.

11. Under what case of Master’s theorem will the recurrence relation of binary search fall?

a) 1
b) 2
c) 3
d) It cannot be solved using the master’s theorem

The recurrence relation of binary search is given by T(n) = T(n/2) + O(1). So we can observe that c = Logba so it will fall under case 2 of master’s theorem.

1. Solve the following recurrence using Master’s theorem.

T(n) = 4T (n/2) + n2

a) T(n) = O(n)
b) T(n) = O(log n)
c) T(n) = O(n2log n)
d) T(n) = O(n2)

The given recurrence can be solved by using the second case of Master’s theorem.
T(n) = O(nc log n) = Here nc = n2

So the solution becomes T(n) = O(n2log n).

2. Solve the following recurrence using Master’s theorem. T(n) = T (n/2) + 2n

a) T(n) = O(n2)
b) T(n) = O(n2 log n)
c) T(n) = O(2n)
d) cannot be solved

The given recurrence can be solved by using the third case (as f(n) > log21) of Master’s theorem.

T(n) = O(f(n)) = Here f(n) = 2n.

So the solution becomes T(n) = O(2n).

3. Solve the following recurrence using Master’s theorem.

T(n) = 16T (n/4) + n

a) T(n) = O(n)
b) T(n) = O(log n)
c) T(n) = O(n2log n)
d) T(n) = O(n2)

The given recurrence can be solved by using the first case of Master’s theorem. So the solution becomes T(n) = O(n2).

4. Solve the following recurrence using Master’s theorem.

T(n) = 2T (n/2) + n/ log n

a) T(n) = O(n)
b) T(n) = O(log n)
c) T(n) = O(n2log n)
d) cannot be solved using the master’s theorem

The given recurrence cannot be solved by using the Master’s theorem. It is because this recurrence relation does not fit into any case of Master’s theorem.

5. Solve the following recurrence using Master’s theorem.

T(n) = 0.7 T (n/2) + 1/n

a) T(n) = O(n)
b) T(n) = O(log n)
c) T(n) = O(n2log n)
d) cannot be solved using master’s theorem

The given recurrence cannot be solved by using the Master’s theorem. It is because in this recurrence relation a < 1 so master’s theorem cannot be applied.

6. Solve the following recurrence using Master’s theorem.
T(n) = 4 T (n/2) + n!

a) T(n) = O(n!)
b) T(n) = O(n! log n)
c) T(n) = O(n2log n)
d) cannot be solved using master’s theorem

The given recurrence can be solved by using the third case of Master’s theorem. So the solution becomes T(n) = O(n!).

7. Solve the following recurrence using Master’s theorem.
T(n) = 4T (n/4) + n log n

a) T(n) = O(n (log n)2)
b) T(n) = O(n log n)
c) T(n) = O(n2log n)
d) cannot be solved using master’s theorem

The given recurrence can be solved by using the extended second case of Master’s theorem. So the solution becomes T(n) = O(n (log n)2).

8. What will be the recurrence relation of the following code?

Int sum(int n)
{
If(n==1)
return 1;
else
return n+sum(n-1);
}

a) T(n) = T(n/2) + n
b) T(n) = T(n-1) + n
c) T(n) = T(n-1) + O(1)
d) T(n) = T(n/2) + O(1)