NEW
Font size
WorksheetsDAA
Total questions: 20
Worksheet time: 10mins
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
To which of the following class does a CNF-satisfiability (say 3-SAT)problem belong?
NP class
P class
NP complete
NP hard
Which of the following problems is NOT solved using dynamic programming?
0/1 knapsack problem
Matrix chain multiplication problem
Edit distance problem
Fractional knapsack problem
A greedy algorithm can be used to solve all the dynamic programming problems.
True
False
What happens when the backtracking algorithm reaches a complete solution?
It backtracks to the root
It continues searching for other possible solutions
It traverses from a different route
Recursively traverses through the same route
..................................... of an undirected graph is to find minimum subset of vertices that cover all the edges.
3-SAT Problem
Clique problem
Boolean problem
vertex cover problem
A graph with 'n' number of vertices is said to be complete if it contains ............number of edges.
n
n-1
n(n-1)/2
n/2
....................... is the act of finding a set of variable assignments to True or False that make that statement true or alternately providing a proof that no such set of variable assignments can exist.
3-SAT Problem
Vertex Cover Problem
Clique problem
Clique decision problem
Clique is a sub-graph of a graph which is complete.
True
False
Dynamic programming differs from the greedy method since the greedy method produces only one feasible solution, which may or may not be optimal, while dynamic programming produces all possible sub-problems at most once, one of which guaranteed to be optimal.
True
False
A...................... is a maximal connected sub-graph of a graph
Component
Connected component
Bi-connected component
none
