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

• D.H Lehmar
• J.D. Ullman
• K.Thompson
• R.E. Bellman
Answer: A
• 32
• 34
• 36
• 38
Answer: D
• Infinite
• 0
• 1
• 2
Answer: A
• 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
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
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