LCS in dynamic programming.

Morningdot Hablu

@morningdot-6Xuj4M • Oct 22, 2024

Oct 22, 2024

1.3K

hi friend's
Anybody have idea about longest subsequence problem of dynamic programming.
😒😒😒

Like 0 Replies 11

Replies

Welcome, guest

Join CrazyEngineers to reply, ask questions, and participate in conversations.

CrazyEngineers powered by Jatra Community Platform

sushant005

@sushant005-tyt4WK • Jun 16, 2010

LCS (Longest common sub sequence) follows Dynamic programming.
In this case we are comparing two input string and finding the longest common sub sequence with greater length as the output. As LCS is following Dynamic problem so it has many problems with greatest and smallest length sub sequence but our optimal solution is only sub sequence with greater length.

For example:-
Let suppose we are given sequence of two input string X and Y where,
X= {a,b,c,b,d,a,b}
and Y= {b,d,c,a,b,a}

Z = {b,c,b,a} is the longest common sub sequence to both X and Y of length 4.
0
Morningdot Hablu

@morningdot-6Xuj4M • Jun 17, 2010

sushant005
longest common sub sequence with greater length as the output.
what it means.

suppose an example.
AGGA is a longest common subsequence of x = AGCGA and y = CAGATAGAG.
where i use this.
0
sushant005

@sushant005-tyt4WK • Jun 17, 2010

LCS as the name suggest that our optimal solution would be longest common sub sequence notice the term longest. As we all know that Dynamic programming is bottom to up approach so first we have find the all possible solutions of the given problem then we have to choose the best one called as optimal solution to the problem.
Same here, here we have many solutions of greater as well as smallest length but our optimal solution is only the sub sequence with the greatest length.
I think now you got it!
0
sushant005

@sushant005-tyt4WK • Jun 17, 2010

mohit007kumar00
what it means.

suppose an example.
AGGA is a longest common subsequence of x = AGCGA and y = CAGATAGAG.
where i use this.

where i use this means.
0
Morningdot Hablu

@morningdot-6Xuj4M • Jun 17, 2010

sushant005
LCS as the name suggest that our optimal solution would be longest common sub sequence notice the term longest. As we all know that Dynamic programming is bottom to up approach so first we have find the all possible solutions of the given problem then we have to choose the best one called as optimal solution to the problem.
Same here, here we have many solutions of greater as well as smallest length but our optimal solution is only the sub sequence with the greatest length.
I think now you got it!
suppose we have to calculate lcs of "class" and "cboy".
then how many possible solutions are there please write the solutions.
0
Morningdot Hablu

@morningdot-6Xuj4M • Jun 17, 2010

sushant005

where i use this means.
I want to know the use of lcs.where it is used?
0
sushant005

@sushant005-tyt4WK • Jun 17, 2010

mohit007kumar00
suppose we have to calculate lcs of "class" and "cboy".
then how many possible solutions are there please write the solutions.
Here there are only one matching i.e c between two strings you mentioned "class" and "cboy".
0
sushant005

@sushant005-tyt4WK • Jun 17, 2010

mohit007kumar00
I want to know the use of lcs.where it is used?
LCS is generally used in DNA matching,file comparison etc.

1>Molecular biology. DNA sequences can be represented as sequences/base of four letters ACGT, corresponding to the four sub molecules forming DNA. One way of computing how similar two sequences are is to find the length of their longest common sub sequence.

2>File comparison. The Unix program "diff" is used to compare two different versions of the same file, to determine what changes have been made to the file. It works by finding a longest common sub sequence of the lines of the two files; any line in the sub sequence has not been changed, then it displays the remaining set of lines that have changed. In this instance of the problem we should think of each line of a file as being a single complicated character in a string.
0
Morningdot Hablu

@morningdot-6Xuj4M • Jun 17, 2010

sushant005
Here there are only one matching i.e c between two strings you mentioned "class" and "cboy".
comman word is always the shortest among them then what is the means of this line.
"optimal solution is only the sub sequence with the greatest length" .
0
vishnu priya

@vishnu-priya-L6wLMl • Jun 17, 2010

LCS seriously a new term to m.Just got to know it!Thanks for posting here mohit!
0
sushant005

@sushant005-tyt4WK • Jun 18, 2010

mohit007kumar00
comman word is always the shortest among them then what is the means of this line.
"optimal solution is only the sub sequence with the greatest length" .
Yes, Mohit you are very right that common word is always the shortest but here our aim is to find the solution to the problem with greatest length.There is procedure to find the solution to the problen is crealy given in Cormen, follows the steps given in Cormen you will surely get it...
0