CrazyEngineers
CrazyEngineers

  • LCS in dynamic programming.

    Morningdot Hablu

    Member

    Updated: Oct 22, 2024
    Views: 1.1K
    hi friend's
    Anybody have idea about longest subsequence problem of dynamic programming.
    😒😒😒
    0
    Replies
Howdy guest!
Dear guest, you must be logged-in to participate on CrazyEngineers. We would love to have you as a member of our community. Consider creating an account or login.
Replies

  • sushant005

    Member • 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.
    Are you sure? This action cannot be undone.
    Cancel

  • Morningdot Hablu

    Member • 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.
    Are you sure? This action cannot be undone.
    Cancel

  • sushant005

    Member • 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!
    Are you sure? This action cannot be undone.
    Cancel

  • sushant005

    Member • 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.
    Are you sure? This action cannot be undone.
    Cancel

  • Morningdot Hablu

    Member • 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.
    Are you sure? This action cannot be undone.
    Cancel

  • Morningdot Hablu

    Member • Jun 17, 2010

    sushant005

    where i use this     means.
    I want to know the use of lcs.where it is used?
    Are you sure? This action cannot be undone.
    Cancel

  • sushant005

    Member • 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".
    Are you sure? This action cannot be undone.
    Cancel

  • sushant005

    Member • 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.
    Are you sure? This action cannot be undone.
    Cancel

  • Morningdot Hablu

    Member • 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" .
    Are you sure? This action cannot be undone.
    Cancel

  • vishnu priya

    Member • Jun 17, 2010

    LCS seriously a new term to m.Just got to know it!Thanks for posting here mohit!
    Are you sure? This action cannot be undone.
    Cancel

  • sushant005

    Member • 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...
    Are you sure? This action cannot be undone.
    Cancel
Home Channels Search Login Register