Design and Analysis of Algorithms Mid  II, November  2014
1.To identify articulation points in a graph _________ is useful.

Game tree

in order traversal

dfs

none

Answer: C
2.The solid edges of the depth first spanning tree of the gragh are called _____ edges.

heavy

light

dark

tree

Answer: D
3.Two biconnected components can have at least _________ in common.

one vertex

two vertices

no vertex

one edge

Answer: A
4.In backtracking _______ constraints are the rules that determine the tuples of solution space.

explicit

implicit

bounding functions

permutation tree

Answer: A
5.The name backtrack was first coined by _____________

lehmer

Ullman

Thompson

bellman

Answer: A
6.If we represent solution space in the form of a __________tree.

BFS

DFS

State space

min cost spanning tree

Answer: C
7.A node is generated but its children not generated called ____ node.

live

dead

expaned

x

Answer: A
8.If n = 4 the possible leaf nodes in the tree organization are ___________

4

8

20

16

Answer: D
9.Branch and bound technique is applicable for ________ problem.

minimization

maximization

reliability

BFS

Answer: A
10.A graph cannot be drawn on a plane without cross over between its edges called ______.

planar

non planar

euler

directed

Answer: B
11.Number of external nodes in a binary tree with n identifiers is ________________.
Answer: Dynamic programming
12.The ______________ states that what ever the intial state and decision are, the remaining decisions must constitute an optimal decision sequence.
Answer: N
13.Each node in the problem state space is called ______________.
Answer: Optimal
14.In nqueens problem nodes are numbered as in ______________.
Answer: Enode
15._____________ constraints describe the way in which xi must relate to each other.
Answer: 24
16.A dead node cannot be __________________,
Answer: State space
17.A dead node cannot be __________________,
Answer: Expanded
18.All deterministic search algorithms have time complexity of ______________.
Answer: Decision problem
19.The computing time for choice, success and failure is _______________
Answer: Polynomial
20.____________ algorithms have the property that the result of every operation is uniquely defined.
Answer: Deterministic