Font size
WorksheetsDAA-UNIT-4 QUIZ
Total questions: 10
Worksheet time: 6mins
Which of the following is not a backtracking algorithm?
N-queens Problem
Task Scheduling Algorithm
Subset Sum Problem
Tower of Hanoi Problem
(a) is an algorithm design method that can be used when the solution to a problem can be viewed as the result of a sequence of decisions
The name backtrack was first coined by _________
D.H.Lehmer
L. Baumert
R.J. Walker
S.Golomb
The term (a) refers to all state space search methods in which all children of the –nodes are generated before any other live node can become the E-node.
Which of the following statements is true for Branch - and - Bound search?
Underestimates of remaining distance may cause deviation from optimal path
Overestimates can't cause right path to be overlooked
Dynamic programming principle can be used to discard redundant partial paths
All of the above
Read the following statements carefully, and choose the correct answer:
I. For the Backtracking algorithms stack data structure is used.
II. For the Branch-and-bound algorithms queue data structure is used.
(I) is FALSE but (II) is TRUE
(I) and (II) both are FALSE
(I) is TRUE but (II) is FALSE
(I) and (II) both are TRUE
(II) is TRUE and (I) can’t be defined.
For the 15-puzzle problem if the initial arrangement is as follows, then the value of ‘x’ used to find the reachability is (a)
Let S be an NP-complete problem and Q and R be two other problems not known to be in NP. Q is polynomial time reducible to S and S is polynomial-time reducible to R. Which one of the following statements is true?
R is NP-complete
R is NP-hard
Q is NP-complete
Q is NP-hard
Choose the correct statement from the following.
branch and bound is more efficient than backtracking
branch and bound is not suitable where a greedy algorithm is not applicable
branch and bound divides a problem into at least 2 new restricted sub problems
backtracking divides a problem into at least 2 new restricted sub problems
"Both LIFO branch and bound strategy and backtracking leads to depth first search.-"The statement is true/false?
(a)
