DAA

Which of the problems cannot be solved by backtracking method?

• n-queen problem

• subset sum problem

• Hamiltonian circuit problem

• travelling salesman problem

Backtracking algorithm is implemented by constructing a tree of choices called as?

• State-space tree

  
  

• state chart tree

• node tree

• Backtracking tree

The problem of finding a path in a graph that visits every vertex exactly once is called?

• Hamiltonian path problem

• Hamiltonian cycle problem

• sum of subset problem

• Turnpike reconstruction problem

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

• Knapsack problem

• closest pair problem

• travelling salesman problem

• assignment problem

The problem of finding a subset of positive integers whose sum is equal to a given positive integer is called as?

• n- queen problem

  
  

• sum of subsets problem

• knapsack problem

• Hamiltonian circuit problem

Branch and bound is a __________

• problem solving technique

• data structure

• sorting algorithm

• type of tree

Choose the correct statement from the following.

• Greedy method is efficient than dynamic programming approach

• Backtracking approach gives only one optimal solution

• Branch and bound can be used for solving Optimization problems

• None of these

Problems that can be solved in polynomial time are known as?

• intractable

• tractable

• decision

• complete

28. _________ is the class of decision problems that can be solved by non-deterministic polynomial algorithms?

• NP

• P

• Hard

• Complete

Problems that can be verified in Polynomial time are called

• P problems

• NP problems

• Tractable problems

• none of these