4th_DAA

Which of the following is not a backtracking algorithm?

• N-queens Problem

• Task Scheduling Algorithm

• Subset Sum Problem

• Tower of Hanoi Problem

Given items as {value,weight} pairs {{40,20},{30,10},{20,5}}. The capacity of knapsack=20. Find the maximum value output assuming items to be divisible.

• 60

• 100

• 80

• 40

Time complexity of fractional knapsack problem is ____________

• O(n log n)

• O(n)

• O(n2)

• O(nW)

In the given graph, identify the shortest path having minimum cost to reach vertex 'e' if 'a' is the source vertex.

• a-b-e

• a-c-e

• a-c-d-e

• a-c-d-b-e

Which of the following can traverse the state space tree only in DFS manner?

• branch and bound

• dynamic programming

• greedy algorithm

  
  

• backtracking

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

For how many queens was the extended version of Eight Queen Puzzle applicable for n*n squares?

• 5

• 8

• N

• 6

How many fundamental solutions are the for 3 queens on a 3*3 board?

• 1

• 3

• 0

• 12

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

• State-space tree

• node tree

• state chart tree

• Backtracking tree

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

• n- queen problem

• knapsack problem

  
  

• sum of subsets problem

• Hamiltonian circuit problem