) Write a dynamic programming algorithm to solve the longest increasing subseque
ID: 3677824 • Letter: #
Question
) Write a dynamic programming algorithm to solve the longest increasing subsequence (LIS) problem. You are given an array a of n integers. An increasing subsequence is a sequence
k indices 0 i1 < i2 < · · · < ik (n 1)
such that a[i1] < a[i2] < · · · < a[ik]
Given a find the longest increasing subsequence. I.e, an increasing subsequence i1, . . . , ik whose length k is the longest possible. Example: Input is a : [1, 5, 2, 3, 8]. The longest increasing subsequence has length 4. i1 = 0, i2 = 2, i3 = 3, i4 = 4 yielding the elements 1, 2, 3, 8. Let us define the function lis(a, j, M) as the length of the LIS for the first j elements of the array (a[0] · · · a[j 1]), where j ranges from 0 to n and all elements of this subsequence are less than M.
(A) For the array a : [1, 5, 2, 3, 8] write down the values of lis(a, 3, 2) and lis(a, 5, ).
(B) Write down the base cases for lis(a, 0, M).
(C) Write down a recurrence for lis(a, j, M) for any j with 1 j n.
(D) Describe a bottom-up scheme to memoize the recurrence lis above. Describe the memo table itself: how many rows? how many columns? what do the rows and columns stand for? How are the base cases filled out in the table? How is each entry of the memo table filled out?
Explanation / Answer
#include<stdio.h>
#include<string.h>
#define maxn 100100
int max(int a,int b)
{
return a>b?a:b;
}
int LongestCommonSubsequence(char S[],char T[])
{
int Slength = strlen(S);
int Tlength = strlen(T);
/* Starting the index from 1 for our convinience (avoids handling special cases for negative indices) */
int iter,jter;
for(iter=Slength;iter>=1;iter--)
{
S[iter] = S[iter-1];
}
for(iter=Tlength;iter>=1;iter--)
{
T[iter] = T[iter-1];
}
int common[Slength+1][Tlength+1];
/* common[i][j] represents length of the longest common sequence in S[1..i], T[1..j] */
/* Recurrence: common[i][j] = common[i-1][j-1] + 1 if S[i]==T[j]
= max(common[i-1][j],common[i][j-1]) otherwise
*/
/*common[0][i]=0, for all i because there are no characters from string S*/
for(iter=0;iter<=Tlength;iter++)
{
common[0][iter]=0;
}
/*common[i][0]=0, for all i because there are no characters from string T*/
for(iter=0;iter<=Slength;iter++)
{
common[iter][0]=0;
}
for(iter=1;iter<=Slength;iter++)
{
for(jter=1;jter<=Tlength;jter++)
{
if(S[iter] == T[jter] )
{
common[iter][jter] = common[iter-1][jter-1] + 1;
}
else
{
common[iter][jter] = max(common[iter][jter-1],common[iter-1][jter]);
}
}
}
return common[Slength][Tlength];
}
int main()
{
char S[maxn],T[maxn];/* S,T are two strings for which we have to find the longest common sub sequence. */
scanf("%s%s",S,T);
printf("%d ",LongestCommonSubsequence(S,T));
}
Rough notes about the Algorithm implemented in the code above:
S,T are two strings for which we have to find the longest common sub sequence. Input the two sequences. Now print the longest common subsequence using LongestCommonSubsequence function.
LongestCommonSubsequence function : This function takes the two sequences (S, T) as arguments and returns the longest common subsequence found.
Store the length of both the subsequences. Slength = strlen(S), Tlength = strlen(T). We will Start with the index from 1 for our convenience (avoids handling special cases for negative indices).
Declare common[Slength][Tlength]. Where, common[i][j] represents length of the longest common sequence in S[1..i], T[1..j].
If there are no characters from string S, common[0][i]=0 for all i or if there are no characters from string T, common[i][0]=0 for all i.
Recurrence: for i=1 to Slength
for j=1 to Tlength
common[i][j] = common[i-1][j-1] + 1, if S[i]=T[j]. Else, common[i][j] = max(common[i-1][j],common[i][j-1]). Where max is a function which takes the two
variables as arguments and returns the maximum of them.
Return common[Slength][Tlength].
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.