1. Name the node which has been generated but none of its children nodes have
been generated in state space tree of backtracking method.

Dead node

Live node

E-Node

State Node

Live node

2. How many nodes are there in a full state space tree with n = 6?

65

64

63

32

63

3. This algorithm scans the list by swapping the entries whenever pair of
adjacent keys are out of desired order.

Insertion sort.

Bubble sort.

Shell sort.

Quick sort.

Bubble sort.

4. The notation is

Symmetric

Reflexive

Transitive

B & C only

Transitive

5. From the following chose the one which belongs to the algorithm paradigm
other than to which others from the following belongs to.

Minimum & Maximum problem

Knapsack problem.

Selection problem.

Merge sort.

Knapsack problem.

6. To calculatec(i, j )’s, w( i, j)’s and r(i, j)’s; the OBST algorithm in worst case takes
the following time.

O(log n)

O (n4)

O (n3)

O (n log n)

O (n3)

7. What is the type of the algorithm used in solving the 4 Queens problem?

Greedy

Dynamic

Branch and Bound

Backtracking.

Backtracking.

8. In Knapsack problem, the best strategy to get the optimal solution, where Pi, Wi is the
Profit, Weight associated with each of the Xith object respectively is to

Arrange the values Pi/Wi in ascending order

Arrange the values Pi/Xi in ascending order

Arrange the values Pi/Wi in descending order

Arrange the values Pi/Xi in descending order

Arrange the values Pi/Xi in descending order

9. Greedy job scheduling with deadlines algorithms’ complexity is defined as

O(N)

Ω( n log n)

O (n2 log n)

O ( n log n)

O(N)

10. The divide and conquer merge sort algorithm’s time complexity can be defined as