# Design and Analysis of Algorithms Solved MCQs

1.

## Recursion is similar to which of the following?

A. switch case
B. loop
C. if-else
D. if elif else
Explanation: recursion is similar to a loop.
2.

## 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
Answer» C. smaller instances of the same problem
Explanation: in recursion, the solution of a problem depends on the solution of smaller instances of the same problem.
3.

## 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
Answer» D. problems without base case
Explanation: problems without base case leads to infinite recursion call. in general, we will assume a base case to avoid infinite recursion call. problems like finding factorial of a number, nth fibonacci number and
4.

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

A. recursion
B. iteration
Explanation: the function counts the number of vowels in a string. in this case the number is vowels is 6.
5.

## 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)
Answer» C. fact(n) = n * fact(n-1)
Explanation: fact(n) = n * fact(n – 1) can be used to find the factorial of a number.
6.

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

A. 5
B. 6
C. 7
D. 8
Explanation: the sixth fibonnaci number is
7.

## Which of the following is not a fibonnaci number?

A. 8
B. 21
C. 55
D. 14
Explanation: 14 is not a fibonnaci number.
8.

## Which of the following option is wrong?

A. fibonacci number can be calculated by using dynamic programming
B. fibonacci number can be calculated by using recursion method
C. fibonacci number can be calculated by using iteration method
D. no method is defined to calculate fibonacci number
Answer» D. no method is defined to calculate fibonacci number
Explanation: fibonacci number can be calculated by using dynamic programming, recursion method, iteration method.
9.

## 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)
Answer» D. f(n) = f(n – 1) + f(n – 2)
Explanation: the relation f(n) = f(n – 1) + f(n – 2) can be used to find the nth fibonacci number.
10.

## 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
Explanation: the sum of first n natural numbers is given by n*(n+1)/2, which is equal to (n+1)c2.
11.

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

A. 24
B. 2
C. 3
D. 16
Explanation: as a * b = gcd (a, b) * lcm (a, b). so b = (144 * 8)/72 = 16.
12.

## 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
Explanation: gcm (greatest common measure), gcf (greatest common factor), hcf (highest common factor) and hcf (highest common divisor) are also known as gcd.
13.

## Which of the following is coprime number?

A. 54 and 24
B. 4 and 8
C. 6 and 12
D. 9 and 28
Explanation: coprime numbers have gcd 1. so 9 and 28 are coprime numbers. while 54
14.

## In terms of 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
Answer» B. multiplication of a ꓵ b terms
Explanation: in terms of 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.
15.

## What is the GCD according to the given Venn Diagram?

A. 2
B. 3
C. 5
D. 6
Explanation: in terms of 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.
16.

## 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
Answer» B. gcd (a-b, b) if a>b
Explanation: 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.
17.

## What is the GCD of 48, 18, 0?

A. 24
B. 2
C. 3
D. 6
Explanation: gcd is largest positive integer that divides each of the integer. so the gcd of 48, 18, 0 is 6.
18.

## Is 9 and 28 coprime number?

A. true
B. false
Explanation: coprime numbers have gcd 1. so 9 and 28 are coprime numbers.
19.

## 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
Explanation: 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 the expression is called bezout’s identity and p, q can be calculated by extended form of euclidean algorithm.
20.

## Is gcd an associative function.

A. true
B. false
Explanation: the gcd function is an associative function as gcd (a, gcd (b, c)) = gcd (gcd (a, b), c).
21.

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

A. james e. nymann
B. riemann
C. thomae
D. euler
Explanation: in the year 1972, james e. nymann showed some result to show the probability and expected value of gcd.
22.

## What is the computational complexity of 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)
Answer» A. o (log a + log b)2)
Explanation: 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 number of bits of a and b.
23.

## LCM is also called as

A. gcd
B. scm
C. gcf
D. hcf
Explanation: gcd (greatest common divisor), gcf (greatest common factor), hcf (highest common factor) is not an alias for lcm. lcm is also called as smallest common multiple(scm).
24.

## What is the LCM of 8 and 13?

A. 8
B. 12
C. 20
D. 104
Explanation: 104 is the smallest positive integer that is divisible by both 8 and 12.
25.

A. 100
B. 102
C. 116
D. 104