Analysis and design of algorithm question bank

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²                                                        b. 2ⁿ                                                        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