Quiznetik
Design and Analysis of Algorithms | Set 5
1. Who invented the inclusion-exclusion principle to solve the Hamiltonian path problem?
A. karp
B. leonard adleman
C. andreas bjorklund
D. martello
Correct : C. andreas bjorklund
2. For a graph of degree three, in what time can a Hamiltonian path be found?
A. o(0.251n)
B. o(0.401n)
C. o(0.167n)
D. o(0.151n)
Correct : A. o(0.251n)
3. What is the time complexity for finding a Hamiltonian path for a graph having N vertices (using permutation)?
A. o(n!)
B. o(n! * n)
C. o(log n)
D. o(n)
Correct : B. o(n! * n)
4. How many Hamiltonian paths does the following graph have?
A. 1
B. 2
C. 3
D. 4
Correct : A. 1
5. How many Hamiltonian paths does the following graph have?
A. 1
B. 2
C. 0
D. 3
Correct : C. 0
6. 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
Correct : B. if all elements of set a are also present in set b
7. 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
Correct : 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
8. 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)
Correct : A. it has an exponential time complexity
9. Subset sum problem is an example of NP- complete problem.
A. true
B. false
Correct : A. true
10. Recursive solution of subset sum problem is faster than dynamic problem solution in terms of time complexity.
A. true
B. false
Correct : B. false
11. 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)
Correct : D. the dynamic programming solution has a time complexity of o(n log n)
12. 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
Correct : B. set of all subsets
13. 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
Correct : 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
14. 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)
Correct : A. it has an exponential time complexity
15. 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)
Correct : D. o(sum*n)
16. Recursive solution of Set partition problem is faster than dynamic problem solution in terms of time complexity.
A. true
B. false
Correct : B. false
17. 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)
Correct : D. o(sum*n)