**Objective Type Questions:**

1. DFS stands for
___________________________________________________

2. BFS stands for
___________________________________________________

3. What is chromatic number?

a. number of colors used to color the graph b. number of distinct colors
used to color the graph

c. number of colors used to color the edge d. number of
colors used to color the vertices

4.
Which
equation of correct to find the maximum profit for knapsack using backtracking?

a.
b=b+(1+(c-m)/w[i])*p[i] b.
b=b+(1-(c-m)/w[i]*p[i])

c.
b=b+(1-(c+m)/w[i])*p[i] d.
b=b+(1-(c-m)/w[i])*p[i]

5. What is the
condition to satisfy to put the remaining queens in non-attacking position in
n-Queen Problem?

a. (x[j] = i) or (abs(x[j]-i)
= abs(j-k)) b.
(x[j] = i) or (abs(x[j]-1) = abs(j-k))

c. (x[j] = i) or
(abs(x[j]-i) = abs(i-k)) d.
(x[i] = j) or (abs(x[j]-i) = abs(j-k))

6. Travelling Sales man Problem can be solved with

a. Euclidian cycle b.
Hamiltonian cycle c.
Graph cycle d.
none

7. How many queens are there in nxn chess board in
non-attacking position?

a. n

^{2}b. 2^{n}c. n d. 2n
8. Which are categories of graph coloring?

a. Edge coloring b.
Vertex coloring c.
both a and b d.
none

9. Which algorithm is used as path finder as heuristic
search technique?

a. A* algorithm b.
B* algorithm c.
both a and b d.
none

10. Which data structure is used in DFS algorithm?

a. Stack b.
Queue d.
Array d.
Tree

11. Which data structure is used in BFS algorithm?

a. Stack b.
Queue d.
Array d.
Tree

**Short Answer Type:**

1. Write algorithm for A* algorithm.

2. Write algorithm for B* algorithm.

3. Write algorithm for DFS algorithm.

4. Write algorithm for BFS algorithm.

5. What is backtracking?

6. Write algorithm for Travelling Salesman Problem.

7. Write the algorithm for knapsack problem.

**Long Answer Type:**

1. Write the problem statement and rationale of knapsack
problem for backtracking. Solve this using knapsack problem to obtain the
maximum profit from below given data

**Profits**P1=10, P2=10, P3=12, P4=18.

**Weights**W1= 2, W2= 4, W3= 6, W4=9;

Capacity of sack
i.e.

**m**=15;
Number of items i.e.

**n**=4;
2. Draw all the possibility of queens in
non-attacking position for 4x4 chess board.

3. Write the algorithm for n-queens problem with the
problem statement and rationale.

4. Use DFS algorithm to solve this and write the DFS
sequence:

5. Use BFS algorithm to solve this and write the BFS
sequence:

5.
What is the chromatic number for below graphs for vertex coloring and edge
coloring? Use R-Red, B-Blue, G-Green, Y-Yellow, O-Orange, etc.

Color vertices |
Color edges |

6. Find the path for Travelling Sales man Problem for the
below graph

## No comments:

Post a Comment