Top 150+ Solved Design and Analysis of Algorithms MCQ Questions Answer
Q. Under what condition any set A will be a subset of B?
a. if all elements of set b are also present in set a
b. if all elements of set a are also present in set b
c. if a contains more elements than b
d. if b contains more elements than a
Q. What is a subset sum problem?
a. finding a subset of a set that has sum of elements equal to a given number
b. checking for the presence of a subset that has sum of elements equal to a given number and printing true or false based on the result
c. finding the sum of elements present in a set
d. finding the sum of all the subsets of a set
Q. Which of the following is true about the time complexity of the recursive solution of the subset sum problem?
a. it has an exponential time complexity
b. it has a linear time complexity
c. it has a logarithmic time complexity
d. it has a time complexity of o(n2)
Q. Which of the following is not true about subset sum problem?
a. the recursive solution has a time complexity of o(2n)
b. there is no known solution that takes polynomial time
c. the recursive solution is slower than dynamic programming solution
d. the dynamic programming solution has a time complexity of o(n log n)
Q. What is meant by the power set of a set?
a. subset of all sets
b. set of all subsets
c. set of particular subsets
d. an empty set
Q. What is the set partition problem?
a. finding a subset of a set that has sum of elements equal to a given number
b. checking for the presence of a subset that has sum of elements equal to a given number
c. checking whether the set can be divided into two subsets of with equal sum of elements and printing true or false based on the result
d. finding subsets with equal sum of elements
Q. Which of the following is true about the time complexity of the recursive solution of set partition problem?
a. it has an exponential time complexity
b. it has a linear time complexity
c. it has a logarithmic time complexity
d. it has a time complexity of o(n2)
Q. What is the worst case time complexity of dynamic programming solution of set partition problem(sum=sum of set elements)?
a. o(n)
b. o(sum)
c. o(n2)
d. o(sum*n)
Q. What will be the auxiliary space complexity of dynamic programming solution of set partition problem(sum=sum of set elements)?
a. o(n log n)
b. o(n2)
c. o(2n)
d. o(sum*n)
Q. Minimum time required to solve 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
Q. Master’s theorem is used for?
a. solving recurrences
b. solving iterative relations
c. analysing loops
d. calculating the time complexity of any code