The GATE Grind

GATE 2009 CS – Question 54

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]. Dynamic programming uses L[M, N], M=m+1, N=n+1, with L[i, j]=l(i, j). Which statement is TRUE?

  1. All L elements must be initialized to0 for l(i, j) to be properly computed.
  2. l(i, j) may be computed in row-major but not column-major order.
  3. l(i, j) can be computed in either row-major or column-major order.
  4. L[p, q] must precede L[r, s] if either p<r or q<s.

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (C) l(i, j) can be computed in either row-major or column-major order.

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 →