The GATE Grind

GATE 2009 CS – Question 53

Algorithms · Dynamic Programming · 2 marks · Multiple choice

A subsequence deletes any number of elements while preserving order. X[m], Y[n] are sequences of lengths m, n, indexed from0. Let l(i, j) be their prefix LCS length: l=0 if i=0 or j=0; l=expr1 if i, j>0 and X[i−1]=Y[j−1]; l=expr2 if i, j>0 and X[i−1]≠Y[j−1]. Which option is correct?

  1. expr1 = l(i−1, j)+1
  2. expr1 = l(i, j−1)
  3. expr2 = max(l(i−1, j), l(i, j−1))
  4. expr2 = max(l(i−1, j−1), l(i, j))

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (C) expr2 = max(l(i−1, j), l(i, j−1))

Explanation

We are sorry we couldn't write detailed soluition for this, we are working on it!, please consider asking your own AI, its just 2-3 clicks with very minimum effort

More Dynamic Programming questions

All Dynamic Programming questions →