Design And Analysis Of Algorithms Set 17 MCQs

Q1 | There is no existing relationship between a Hamiltonian path problem and Hamiltonian circuit problem.

true
false

Answer: false

Explaination:
there is a relationship between hamiltonian path problem and hamiltonian circuit problem. the hamiltonian path in graph g is equal to hamiltonian cycle in graph h under certain conditions.

Q2 | Which of the following problems is similar to that of a Hamiltonian path problem?

knapsack problem
closest pair problem
travelling salesman problem
assignment problem

Answer: travelling salesman problem

Explaination:
hamiltonian path problem is similar to that of a travelling salesman problem since both the problem traverses all the nodes in a graph exactly once.

Q3 | Who formulated the first ever algorithm for solving the Hamiltonian path problem?

martello
monte carlo
leonard
bellman

Answer: martello

Explaination:
the first ever problem to solve the hamiltonian path was the enumerative algorithm formulated by martello.

Q4 | In what time can the Hamiltonian path problem can be solved using dynamic programming?

o(n)
o(n log n)
o(n2)
o(n2 2n)

Answer: o(n2 2n)

Explaination:
using dynamic programming, the time taken to solve the hamiltonian path problem is mathematically found to be o(n2 2n).

Q5 | In graphs, in which all vertices have an odd degree, the number of Hamiltonian cycles through any fixed edge is always even.

true
false

Answer: true

Explaination:
according to a handshaking lemma, in graphs, in which all vertices have an odd degree, the number of hamiltonian cycles through any fixed edge is always even.

Q6 | Who invented the inclusion-exclusion principle to solve the Hamiltonian path problem?

karp
leonard adleman
andreas bjorklund
martello

Answer: andreas bjorklund

Explaination:
andreas bjorklund came up with the inclusion-exclusion principle to reduce the counting of number of hamiltonian cycles.

Q7 | For a graph of degree three, in what time can a Hamiltonian path be found?

o(0.251n)
o(0.401n)
o(0.167n)
o(0.151n)

Answer: o(0.251n)

Explaination:
for a graph of maximum degree three, a hamiltonian path can be found in time o(0.251n).

Q8 | What is the time complexity for finding a Hamiltonian path for a graph having N vertices (using permutation)?

o(n!)
o(n! * n)
o(log n)
o(n)

Answer: o(n! * n)

Explaination:
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).

Q9 | How many Hamiltonian paths does the following graph have?

1
2
3
4

Answer: 1

Explaination:
the above graph has only one hamiltonian path that is from a-b-c-d-e.

Q10 | Under what condition any set A will be a subset of B?

if all elements of set b are also present in set a
if all elements of set a are also present in set b
if a contains more elements than b
if b contains more elements than a

Answer: if all elements of set a are also present in set b

Explaination:
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.

Q11 | What is a subset sum problem?

finding a subset of a set that has sum of elements equal to a given number
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
finding the sum of elements present in a set
finding the sum of all the subsets of a set

Answer: 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

Explaination:
in subset sum problem check for the presence of a subset that has sum of elements equal to a given number. if such a

Q12 | Which of the following is true about the time complexity of the recursive solution of the subset sum problem?

it has an exponential time complexity
it has a linear time complexity
it has a logarithmic time complexity
it has a time complexity of o(n2)

Answer: it has an exponential time complexity

Explaination:
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.

Q13 | Subset sum problem is an example of NP- complete problem.

true
false

Answer: true

Explaination:
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.

Q14 | Recursive solution of subset sum problem is faster than dynamic problem solution in terms of time complexity.

true
false

Answer: false

Explaination:
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.

Q15 | Which of the following is not true about subset sum problem?

the recursive solution has a time complexity of o(2n)
there is no known solution that takes polynomial time
the recursive solution is slower than dynamic programming solution
the dynamic programming solution has a time complexity of o(n log n)

Answer: the dynamic programming solution has a time complexity of o(n log n)

Explaination:
recursive solution of subset sum problem is slower than dynamic problem solution in terms of time complexity.

Q16 | What is meant by the power set of a set?

subset of all sets
set of all subsets
set of particular subsets
an empty set

Answer: set of all subsets

Explaination:
power set of a set is defined as the set of all subsets. ex- if there is a set s=

Q17 | What is the set partition problem?

finding a subset of a set that has sum of elements equal to a given number
checking for the presence of a subset that has sum of elements equal to a given number
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
finding subsets with equal sum of elements

Answer: 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

Explaination:
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.

Q18 | Which of the following is true about the time complexity of the recursive solution of set partition problem?

it has an exponential time complexity
it has a linear time complexity
it has a logarithmic time complexity
it has a time complexity of o(n2)

Answer: it has an exponential time complexity

Explaination:
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.

Q19 | What is the worst case time complexity of dynamic programming solution of set partition problem(sum=sum of set elements)?

o(n)
o(sum)
o(n2)
o(sum*n)

Answer: o(sum*n)

Explaination:
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.

Q20 | Recursive solution of Set partition problem is faster than dynamic problem solution in terms of time complexity.

true
false

Answer: false

Explaination:
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.

Q21 | What will be the auxiliary space complexity of dynamic programming solution of set partition problem(sum=sum of set elements)?

o(n log n)
o(n2)
o(2n)
o(sum*n)

Answer: o(sum*n)

Explaination:
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).