McqMate
| 401. |
Who invented the inclusion-exclusion principle to solve the Hamiltonian path problem? |
| A. | karp |
| B. | leonard adleman |
| C. | andreas bjorklund |
| D. | martello |
| Answer» C. andreas bjorklund | |
| Explanation: andreas bjorklund came up with the inclusion-exclusion principle to reduce the counting of number of hamiltonian cycles. | |
| 402. |
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) |
| Answer» A. o(0.251n) | |
| Explanation: for a graph of maximum degree three, a hamiltonian path can be found in time o(0.251n). | |
| 403. |
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) |
| Answer» B. o(n! * n) | |
| Explanation: for a graph having n vertices traverse the permutations in n! iterations and it traverses the permutations to see if adjacent vertices are connected or not takes n iterations (i.e.) o(n! * n). | |
| 404. |
How many Hamiltonian paths does the following graph have? |
| A. | 1 |
| B. | 2 |
| C. | 3 |
| D. | 4 |
| Answer» A. 1 | |
| Explanation: the above graph has only one hamiltonian path that is from a-b-c-d-e. | |
| 405. |
How many Hamiltonian paths does the following graph have? |
| A. | 1 |
| B. | 2 |
| C. | 0 |
| D. | 3 |
| Answer» C. 0 | |
| Explanation: the above graph has no hamiltonian paths. that is, we cannot traverse the graph with meeting vertices exactly once. | |
| 406. |
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 |
| Answer» B. if all elements of set a are also present in set b | |
| Explanation: any set a will be called a subset of set b if all elements of set a are also present in set b. so in such a case set a will be a part of set b. | |
| 407. |
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 |
| Answer» 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 | |
| Explanation: in subset sum problem check for the presence of a subset that has sum of elements equal to a given number. if such a | |
| 408. |
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) |
| Answer» A. it has an exponential time complexity | |
| Explanation: subset sum problem has both recursive as well as dynamic programming solution. the recursive solution has an exponential time complexity as it will require to check for all subsets in worst case. | |
| 409. |
Subset sum problem is an example of NP- complete problem. |
| A. | true |
| B. | false |
| Answer» A. true | |
| Explanation: subset sum problem takes exponential time when we implement a recursive solution. subset sum problem is known to be a part of np complete problems. | |
| 410. |
Recursive solution of subset sum problem is faster than dynamic problem solution in terms of time complexity. |
| A. | true |
| B. | false |
| Answer» B. false | |
| Explanation: the recursive solution to subset sum problem takes exponential time complexity whereas the dynamic programming solution takes polynomial time complexity. so dynamic programming solution is faster in terms of time complexity. | |
| 411. |
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) |
| Answer» D. the dynamic programming solution has a time complexity of o(n log n) | |
| Explanation: recursive solution of subset sum problem is slower than dynamic problem solution in terms of time complexity. | |
| 412. |
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 |
| Answer» B. set of all subsets | |
| Explanation: power set of a set is defined as the set of all subsets. ex- if there is a set s= | |
| 413. |
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 |
| Answer» 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 | |
| Explanation: in set partition problem we check whether a set can be divided into 2 subsets such that the sum of elements in each subset is equal. if such subsets are present then we print true otherwise false. | |
| 414. |
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) |
| Answer» A. it has an exponential time complexity | |
| Explanation: set partition problem has both recursive as well as dynamic programming solution. the recursive solution has an exponential time complexity as it will require to check for all subsets in the worst case. | |
| 415. |
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) |
| Answer» D. o(sum*n) | |
| Explanation: set partition problem has both recursive as well as dynamic programming solution. the dynamic programming solution has a time complexity of o(n*sum) as it as a nested loop with limits from 1 to n and 1 to sum respectively. | |
| 416. |
Recursive solution of Set partition problem is faster than dynamic problem solution in terms of time complexity. |
| A. | true |
| B. | false |
| Answer» B. false | |
| Explanation: the recursive solution to set partition problem takes exponential time complexity whereas the dynamic programming solution takes polynomial time complexity. so dynamic programming solution is faster in terms of time complexity. | |
| 417. |
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) |
| Answer» D. o(sum*n) | |
| Explanation: the auxiliary space complexity of set partition problem is required in order to store the partition table. it takes up a space of n*sum, so its auxiliary space requirement becomes o(n*sum). | |
Done Reading?