Analysis and Design of Algorithm question bank

Objective Type Questions:

1. Which one is the correct equation for Fibonacci sequence by Dynamic Programming?

a. F[n]=F[n-1]+F[n-2]                        b. F_n=F_n-1+F_n-2                                       c. F(n)=F(n-1)+F(n-2)                        d. All of these

2. Which equation is correct when a character is matched in Longest Common Subsequence problem?

a. c[i,j]=c[i,j-1]                                     b. c[i,j]=c[i-1,j-1]                                 c. c[i,j]=c[i-1,j]                                     d. None of these

3. Which equation is correct to multiply matrix in Matrix Chain Multiplication problem?

a. m[i,j]=min(m[i,k+1]+m[k+1,j]+p_i-1p_kp_j)                                                    b. m[i,j]=min(m[i,k]+m[k+1,j+1]+p_i-1p_kp_j+1)

c. m[i,j]=min(m[i,k]+m[k+1,j]+p_i-1p_kp_j)                                                        d. m[i,j]=min(m[i,k]+m[k+1,j]+p_i-1p_k-1p_j)

4. Dynamic Programming uses_____________

a. Store-and-forward                           b. greedy method                                c. brute-force                                        d. none

5. How many spanning tree T can be designed for the graph G with ‘n’ node?

a. 2ⁿ                                                        b. 2n                                                       c. n^2-n                                                      d. n²-n

6. In this algorithm the edges has to be considered to make minimal spanning tree.

a. Prim’s algorithm                             b. Kruskal’s algorithm                       c. Dijikstra’s algorithm                      d. none

7. In this algorithm the vertices has to be considered to make minimal spanning tree.

a. Prim’s algorithm                             b. Kruskal’s algorithm                       c. Dijikstra’s algorithm                      d. none

8. Huffman coding is an example of

a. Greedy algorithm                            b. variable length coding                   c. both a and b                                      d. none

9. LCS stands for_________________________

a. Longest common subsequence                                                                    b. longest common substring

c. longest common string                                                                                  d. longest common sequence

10. Floyd-Warshall algorithm uses this algorithm.

a. Prim’s algorithm                             b. Kruskal’s algorithm                       c. Dijikstra’s algorithm                      d. none

Short Answer Type:

1. Rationalize Fibonacci sequence for dynamic programming.

2. Find LCS for text1=MZJAWXU, text2=XMJYAUZ.

3. What are the elements of Dynamic Programming, write them? What is optimal solution?

4. Draw only Huffman tree for

A	E	I	O	U
2	3	5	7	9

5. Draw only minimal spanning tree for below graph, manually.

6. What is the shortest distance from a to g, manually.

7. There are 4 matrices to be multiply A, B, C, D, how many combinations are there to multiply them, write the combinations.

8. What is the difference between greedy approach and dynamic programming.

9. What is the difference between Prim’s and Kruskal’s algorithm for minimal spanning tree.

10. If the size of matrices; A=10X30, B=30x5 and C=5X60, determine the ordering for minimum scalar multiplication.

Long Answer Type:

1. What is the shortest distance from a to g using Dijkstra’s algorithm.

2. Draw only minimal spanning tree for below graph using Kruskal’s or Prim’s algorithm

3. If the size of matrices; A=10X30, B=30x5 and C=5X60, determine the ordering for minimum scalar multiplication using dynamic programming.

4. Find shortest path from A to H using Dijkstra’s algorithm