Design and Analysis of Algorithms Mid - II, April - 2012

1.The name backtrack was first coined by
  • D.H Lehmar
  • J.D. Ullman
  • K.Thompson
  • R.E. Bellman
Answer: A
2.If M=15, n=4, =(10,10,12,18) and =(2,4,6,9) of 0/1 knapsack problem then the maximum profit is
  • 32
  • 34
  • 36
  • 38
Answer: D
3.In branch-and-bound method, for nodes representing infeasible solutions, C(x) =
  • Infinite
  • 0
  • 1
  • 2
Answer: A
4.__________ Functions find a live node with least cost function in LC search
  • minimum()
  • Maximum()
  • Least()
  • Search()
Answer: C
6.We start at a particular node in the graph, visiting all nodes exactly once and come back to initial node with minimum cost is known as
  • 0/1 knapsack problem
  • Optimal storage on tapes
  • Minimum cost spanning tree
  • Travelling sales person problem
Answer: D
7.For infinite state space trees with no answer nodes
  • LC search will terminate
  • LC search will not terminate
  • LC search can not be conducted
  • Termination of LC search depends on cost function
Answer: A
8.The FIFO search coupled with bounding functions is called as
  • FIFOBB
  • Least count search
  • Cumulative reduction function
  • Column reduction
Answer: A
9.NP complete stands for
  • Natural polynomial time complete
  • Non polynomial time complete
  • N-power time complete
  • Non deterministic polynomial time complete
Answer: D
10.Only _________ can be NP complete
  • Linear problems
  • Non linear problems
  • Decision problems
  • Hard problems
Answer: C
11.Tractability means ____________.
Answer: Practically useful algorithm
12.____________ is the set of decision problems that can be solved by a deterministic machine in a polynomial time.
Answer: Complexity class P
13.____________ process in one whose behavior is non deterministic i.e, the next state of the environment is not fully determined by the previous state of the environment.
Answer: Stochastic
14.In FIFOBB square node indicates ___________.
Answer: Answer nodes
15.The LC branch and bound search of a tree will begin with upper _________.
Answer: 0
16.An optimal solution is a feasible solution with _______.
Answer: Maximum value
17.In branch and bound method the three common search strategies are ____________, __________________ and ____________.
Answer: FIFO, LIFO and LC
18.In FIFOBB initially the queue of live nodes is __________.
Answer: Empty
19.A problem is intractable if all algorithms to solve that problem are of atleast __________.
Answer: Exponential time complexity
20.In __________ algorithms, the result of every operation is uniquely defined.
Answer: deterministic