unit-3

A sub-sequence of a given sequence is just the given sequence with some elements (possibly none or all) left out. We are given two sequences X[m] and Y[n] of lengths m and n, respectively, with indexes of X and Y starting from 0.

We wish to find the length of the longest common sub-sequence (LCS) of X[m] and Y[n] as l(m,n), where an incomplete recursive definition for the function l(i,j) to compute the length of the LCS of X[m] and Y[n] is given below:

l(i,j) = 0, if either i=0 or j=0

= expr1, if i,j>0 and X[i - 1] = Y[j - 1]

= expr2, if i,j>0 and X[i - 1] ≠ Y[j - 1]

• A) expr1 ≡ l(i-1,j) + 1

• (B) expr1 ≡≡ l(i,j-1)

• C) expr2 ≡≡ max(l(i-1,j),l(i,j-1)

• (D) expr2 ≡

  ≡ max(l(i-1,j-1),l(i,j))

What happens when a top-down approach of dynamic programming is applied to any problem?

• It increases both, the time complexity and the space complexity

• It increases the space complexity and decreases the time complexity

• It increases the time complexity and decreases the space complexity

• It decreases both, the time complexity and the space complexity

Consider a weighted complete graph G on the vertex set {v1, v2, ..vn} such that the weight of the edge (vi, vj) is 2

|

i

−

j

|

2|i−j|

. The weight of a minimum spanning tree of G is:

• n-1

• 2n-2

• n\2

• n²

Which of the following is true about Kruskal and Prim MST algorithms? Assume that Prim is implemented for adjacency list representation using Binary Heap and Kruskal is implemented using union by rank.

• Worst case time complexity of both algorithms is same

• Worst case time complexity of Kruskal is better than Prim

• Worst case time complexity of Prim is better than Kruskal