Objective Type Questions:
1.
Which one is the correct equation for Fibonacci sequence by Dynamic
Programming?
a.
F[n]=F[n1]+F[n2] b.
F_{n}=F_{n1}+F_{n2} c. F(n)=F(n1)+F(n2) 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,j1] b.
c[i,j]=c[i1,j1] c. c[i,j]=c[i1,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_{i1}p_{k}p_{j}) b.
m[i,j]=min(m[i,k]+m[k+1,j+1]+p_{i1}p_{k}p_{j+1})
c.
m[i,j]=min(m[i,k]+m[k+1,j]+p_{i1}p_{k}p_{j}) d.
m[i,j]=min(m[i,k]+m[k+1,j]+p_{i1}p_{k1}p_{j})
4.
Dynamic Programming uses_____________
a.
Storeandforward b.
greedy method c.
bruteforce d.
none
5. How many spanning tree T can be designed for the graph
G with ‘n’ node?
a. 2^{n} b.
2n c.
n^{2n} d.
n^{2}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. FloydWarshall 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
No comments:
Post a Comment