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 DYNAMICPRO GRAMMING 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.

Explanation / Answer

Using recursive approach -

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
int max(int a, int b);
int fun( char *A, char *B, int m, int n );
//returns lenghth of the longest common subsequence
int main()
{
char A[100],B[100];
printf("Enter first string ");
gets(A);
printf("Enter second string ");
gets(B);
int m = strlen(A);
int n = strlen(B);
  
printf("Length of the longest common subsequence obtained from both of the strings is %d ", fun(A,B,m,n));

return 0;
}

int fun( char *A, char *B, int m, int n )
{
if (m ==0||n==0)
return 0;
if (A[m-1]==B[n-1])
return 1+fun(A,B, m-1, n-1);
else
return max(fun(A,B,m,n-1),fun(A,B,m-1,n));
}

int max(int a, int b)
{
return (a > b)? a : b;
}

Time compexity = 2n in worst case when all of the character are mismatched of both of the strings.

Dynamic Solution -

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
int max(int a, int b);
int fun( char *A, char *B, int m, int n );
//returns lenghth of the longest common subsequence
int main()
{
char A[100],B[100];
printf("Enter first string ");
gets(A);
printf("Enter second string ");
gets(B);
  
int m = strlen(A);
int n = strlen(B);
  
printf("Length of the longest common subsequence obtained from both of the strings is %d ", fun(A,B,m,n));

return 0;
}

int fun( char *A, char *B, int m, int n )
{
int M[m+1][n+1];
int i, j;
for (i=0; i<=m; i++)
{
for (j=0; j<=n; j++)
{
if (i == 0 || j == 0)
M[i][j] = 0;

else if (A[i-1] == B[j-1])
M[i][j] = M[i-1][j-1] + 1;
  
else
M[i][j] = max(M[i-1][j],M[i][j-1]);
}
}
  
/* M[m][n] will contains lengths of Longest Common Subsequence for A[0..n-1] and B[0..m-1] */
return M[m][n];
}
  
int max(int a, int b)
{
return (a > b)? a : b;
}

Time Complexity of the above implementation is O(m*n) which is much better than the worst case time complexity of Recursive implementation that was 2n

These programs are written in C language and to compile follow command -> gcc filenname.c

to execute the program follow command -> ./a.out

GCC Compiler is used in the compilation process.

There will be some warnings that gets() function is dangerous , ignore them :)

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

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