This series of exercises asks you to develop efficient algorithms to find optima

Question

This series of exercises asks you to develop efficient algorithms to find optimal subsequences of various kinds. A subsequence is anything obtained from a sequence by extracting a subset of elements, but keeping them in the same order; the elements of the subsequence need not be contiguous in the original sequence. For example, the strings C, DAMN, YAIOAI, and DYNAMICPROGRAMMING are all subsequences of the string DYNAMICPROGRAMMING.

(a) Let A[1 .. m] and B[1 .. n] be two arbitrary arrays. A common subsequence of A and B is another sequence that is a subsequence of both A and B. Describe an efficient algorithm to compute the length of the longest common subsequence of A and B.

(g) Call a sequence X[1 .. n] of numbers weakly increasing if each element is larger than the average of the two previous elements; that is, 2 · X[i] > X[i 1] + X[i 2] for all i > 2. Describe an efficient algorithm to compute the length of the longest weakly increasing subsequence of an arbitrary array A of integers.

Explanation / Answer

Please find Algorithm and explanation for Q a)

Please repost other question in separate post.

Let the input sequences be X[0..m-1] and Y[0..n-1] of lengths m and n respectively.
And let L(X[0..m-1], Y[0..n-1]) be the length of LCS of the two sequences X and Y.

Following is the recursive definition of L(X[0..m-1], Y[0..n-1]).

   If last characters of both sequences match (or X[m-1] == Y[n-1]) then
       L(X[0..m-1], Y[0..n-1]) = 1 + L(X[0..m-2], Y[0..n-2])

   If last characters of both sequences do not match (or X[m-1] != Y[n-1]) then
       L(X[0..m-1], Y[0..n-1]) = MAX ( L(X[0..m-2], Y[0..n-1]), L(X[0..m-1], Y[0..n-2])

Time complexity of the above naive recursive approach is O(2^n) in worst case and worst case happens when all characters of X and Y mismatch i.e., length of LCS is 0.

Considering the above implementation, following is a partial recursion tree for input strings “AXYT” and “AYZX”

       lcs("AXYT", "AYZX")
       /
       lcs("AXY", "AYZX") lcs("AXYT", "AYZ")
       / /
       lcs("AX", "AYZX") lcs("AXY", "AYZ") lcs("AXY", "AYZ") lcs("AXYT", "AY")

In the above partial recursion tree, lcs(“AXY”, “AYZ”) is being solved twice. If we draw the complete recursion tree, then we can see that there are many subproblems which are solved again and again.
Recomputation of same subproblems can be avoided by either using Memoization or Tabulation.
Following is a tabulated implementation for the LCS problem.

/* Returns length of LCS for X[0..m-1], Y[0..n-1] */
int lcs( char *X, char *Y, int m, int n )
{
int L[m+1][n+1];
int i, j;
  
/* Following steps build L[m+1][n+1] in bottom up fashion. Note
that L[i][j] contains length of LCS of X[0..i-1] and Y[0..j-1] */
for (i=0; i<=m; i++)
{
for (j=0; j<=n; j++)
{
if (i == 0 || j == 0)
L[i][j] = 0;
  
else if (X[i-1] == Y[j-1])
L[i][j] = L[i-1][j-1] + 1;
  
else
L[i][j] = max(L[i-1][j], L[i][j-1]);
}
}
  
/* L[m][n] contains length of LCS for X[0..n-1] and Y[0..m-1] */
return L[m][n];
}
  
/* Utility function to get max of 2 integers */
int max(int a, int b)
{
return (a > b)? a : b;
}

Time Complexity of the above implementation is O(mn) which is much better than the worst case time complexity of Naive Recursive implementation.

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.