Assignment 4: Write a program to implement longest common subsequence (Dynamic Programming) and verify the complexity.

Problem Statement: Write a program to implement longest common subsequence (Dynamic Programming) and verify the complexity.

Theory : The naïve solution for this problem is to generate all subsequences of both given sequences and find the longest matching subsequence. This solution is exponential in terms of time complexity. The general recursive solution of the problem is to generate all subsequences of both given sequences and find the longest matching subsequence. Total possible combinations will be 2n. Hence a recursive solution will take O(2n).

Dynamic Programming Using Memorization :

A common point of observation to use memorization in the recursive code will be the two non-constant arguments M and N in every function call. The function has 4 arguments, but 2 arguments are constant which do not affect the Memorization. The repetitive calls occur for N and M which have been called previously. Following the below steps will help us to write the DP solution using memorization. 1. Use a 2-D array to store the computed lcs(m, n) value at arr[m-1][n-1] as the string index starts from 0. 2. Whenever the function with the same argument m and n are called again, do not perform any further recursive call and return arr[m-1][n-1] as the previous computation of the lcs(m, n) has already been stored in arr[m-1][n-1], hence reducing the recursive calls that happen more than once. Time Complexity: O(N * M), where N and M is the length of the first and second string respectively. Auxiliary Space: (N * M)

Steps-

1.   Create a table of dimension n+1*m+1 where n and m are the lengths of X and Y respectively. The first row and the first column are filled with zeros.

2.      Fill each cell of the table using the following logic.

3.      If the character corresponding to the current row and current column are matching, then fill the current cell by adding one to the diagonal element. Point an arrow to the diagonal cell.

4.      Else take the maximum value from the previous column and previous row element for filling the current cell. Point an arrow to the cell with maximum value. If they are equal, point to any of them.

5.      Step 2 is repeated until the table is filled.

6.      The value in the last row and the last column is the length of the longest common subsequence.

7.      In order to find the longest common subsequence, start from the last element and follow the direction of the arrow. The elements corresponding to () symbol form the longest common subsequence.

Time taken by a dynamic approach is the time taken to fill the table (ie. O(mn)). Whereas, the recursion algorithm has the complexity of 2^max(m, n).

Code

#include<iostream>

#include<cstring>

#include<algorithm>

using namespace std;

int LCS(char *A,char *B, int m, int n){

int lcs[m+1][n+1];

for(int i = 0; i<=m; i++){

for(int j=0;j<=n;j++){

if(i == 0 || j == 0){

lcs[i][j] = 0;

}

else if(A[i-1] == B [j -1]){

lcs[i][j] = 1 + lcs[i-1][j-1];

}

else {

lcs[i][j] = max(lcs[i-1][j],lcs[i][j-1]);

}

}

}

return lcs[m][n];

}

int main(){

char A[] = "stone";

char B[] = "longest";

int i = strlen(A);

int j = strlen(B);

int lcs = LCS(A,B,i,j);

cout<<"\nLCS of given string is :"<<lcs;

cout<<endl;

return 0;

}

Output