LCS in dynamic programming.

Replies

• 

  sushant005

  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.
• 

  Morningdot Hablu

  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.
• 

  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!
• 

  sushant005

  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.
• 

  Morningdot Hablu

  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.
• 

  Morningdot Hablu

  sushant005

  
  where i use this means.

  I want to know the use of lcs.where it is used?
• 

  sushant005

  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".
• 

  sushant005

  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.
• 

  Morningdot Hablu

  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" .
• 

  vishnu priya

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

  sushant005

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