DAA-UNIT-4 QUIZ

Which of the following is not a backtracking algorithm?

• N-queens Problem

• Task Scheduling Algorithm

• Subset Sum Problem

• Tower of Hanoi Problem

____________ 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 ________ 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 ________

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?