Design And Analysis Of Algorithms Set 1

Computer Science Engineering (CSE)

Practice Mode Next
On This Page

This set of Design and Analysis of Algorithms Multiple Choice Questions & Answers (MCQs) focuses on Design And Analysis Of Algorithms Set 1

Q1 | Recursion is similar to which of the following?
  • switch case
  • loop
  • if-else
  • if elif else
Answer: loop
Explaination:
recursion is similar to a loop.
Q2 | Recursion is a method in which the solution of a problem depends on
  • larger instances of different problems
  • larger instances of the same problem
  • smaller instances of the same problem
  • smaller instances of different problems
Answer: smaller instances of the same problem
Explaination:
in recursion, the solution of a problem depends on the solution of smaller instances of the same problem.
Q3 | Which of the following problems can’t be solved using recursion?
  • factorial of a number
  • nth fibonacci number
  • length of a string
  • problems without base case
Answer: problems without base case
Explaination:
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
Q4 | In general, which of the following methods isn’t used to find the factorial of a number?
  • recursion
  • iteration
Answer: recursion
Explaination:
the function counts the number of vowels in a string. in this case the number is vowels is 6.
Q5 | Which of the following recursive formula can be used to find the factorial of a number?
  • fact(n) = n * fact(n)
  • fact(n) = n * fact(n+1)
  • fact(n) = n * fact(n-1)
  • fact(n) = n * fact(1)
Answer: fact(n) = n * fact(n-1)
Explaination:
fact(n) = n * fact(n – 1) can be used to find the factorial of a number.
Q6 | Suppose the first fibonnaci number is 0 and the second is 1. What is the sixth fibonnaci number?
  • 5
  • 6
  • 7
  • 8
Answer: 5
Explaination:
the sixth fibonnaci number is
Q7 | Which of the following is not a fibonnaci number?
  • 8
  • 21
  • 55
  • 14
Answer: 14
Explaination:
14 is not a fibonnaci number.
Q8 | Which of the following option is wrong?
  • fibonacci number can be calculated by using dynamic programming
  • fibonacci number can be calculated by using recursion method
  • fibonacci number can be calculated by using iteration method
  • no method is defined to calculate fibonacci number
Answer: no method is defined to calculate fibonacci number
Explaination:
fibonacci number can be calculated by using dynamic programming, recursion method, iteration method.
Q9 | Which of the following recurrence relations can be used to find the nth fibonacci number?
  • f(n) = f(n) + f(n – 1)
  • f(n) = f(n) + f(n + 1)
  • f(n) = f(n – 1)
  • f(n) = f(n – 1) + f(n – 2)
Answer: f(n) = f(n – 1) + f(n – 2)
Explaination:
the relation f(n) = f(n – 1) + f(n – 2) can be used to find the nth fibonacci number.
Q10 | Which of the following gives the sum of the first n natural numbers?
  • nc2
  • (n-1)c2
  • (n+1)c2
  • (n+2)c2
Answer: (n+1)c2
Explaination:
the sum of first n natural numbers is given by n*(n+1)/2, which is equal to (n+1)c2.
Q11 | If GCD of two number is 8 and LCM is 144, then what is the second number if first number is 72?
  • 24
  • 2
  • 3
  • 16
Answer: 16
Explaination:
as a * b = gcd (a, b) * lcm (a, b). so b = (144 * 8)/72 = 16.
Q12 | Which of the following is also known as GCD?
  • highest common divisor
  • highest common multiple
  • highest common measure
  • lowest common multiple
Answer: highest common divisor
Explaination:
gcm (greatest common measure), gcf (greatest common factor), hcf (highest common factor) and hcf (highest common divisor) are also known as gcd.
Q13 | Which of the following is coprime number?
  • 54 and 24
  • 4 and 8
  • 6 and 12
  • 9 and 28
Answer: 9 and 28
Explaination:
coprime numbers have gcd 1. so 9 and 28 are coprime numbers. while 54
Q14 | In terms of Venn Diagram, which of the following expression gives GCD (Given A ꓵ B ≠ Ø)?
  • multiplication of a u b terms
  • multiplication of a ꓵ b terms
  • multiplication of a*b terms
  • multiplication of a-b terms
Answer: multiplication of a ꓵ b terms
Explaination:
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.
Q15 | What is the GCD according to the given Venn Diagram?
  • 2
  • 3
  • 5
  • 6
Answer: 5
Explaination:
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.
Q16 | What is the GCD of a and b?
  • a + b
  • gcd (a-b, b) if a>b
  • gcd (a+b, a-b)
  • a – b
Answer: gcd (a-b, b) if a>b
Explaination:
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.
Q17 | What is the GCD of 48, 18, 0?
  • 24
  • 2
  • 3
  • 6
Answer: 6
Explaination:
gcd is largest positive integer that divides each of the integer. so the gcd of 48, 18, 0 is 6.
Q18 | Is 9 and 28 coprime number?
  • true
  • false
Answer: true
Explaination:
coprime numbers have gcd 1. so 9 and 28 are coprime numbers.
Q19 | 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?
  • bezout’s identity
  • multiplicative identity
  • sum of product
  • product of sum
Answer: bezout’s identity
Explaination:
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.
Q20 | Is gcd an associative function.
  • true
  • false
Answer: true
Explaination:
the gcd function is an associative function as gcd (a, gcd (b, c)) = gcd (gcd (a, b), c).
Q21 | Who gave the expression for the probability and expected value of gcd?
  • james e. nymann
  • riemann
  • thomae
  • euler
Answer: james e. nymann
Explaination:
in the year 1972, james e. nymann showed some result to show the probability and expected value of gcd.
Q22 | What is the computational complexity of Binary GCD algorithm where a and b are integers?
  • o (log a + log b)2)
  • o (log (a + b))
  • o (log ab)
  • o (log a-b)
Answer: o (log a + log b)2)
Explaination:
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.
Q23 | LCM is also called as                  
  • gcd
  • scm
  • gcf
  • hcf
Answer: scm
Explaination:
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).
Q24 | What is the LCM of 8 and 13?
  • 8
  • 12
  • 20
  • 104
Answer: 104
Explaination:
104 is the smallest positive integer that is divisible by both 8 and 12.
Q25 | Which is the smallest number of 3 digits that is divisible by 2, 4, 8?
  • 100
  • 102
  • 116
  • 104
Answer: 104
Explaination:
lcm of 2, 4, 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, 8.
Next