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 branchandbound 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

Npower 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