29 Nov 2013

DP: Longest Common Sub-Sequence

Problem Statement:
    Find the LCS or Longest Common Sub-sequence (not necessarily contiguous) of the two given Sequences.

Seq 1: P R A T E E K
Seq 2: R A T H O R E

LCS is : R A T E

  Solution :

LCS applications:
1. Molecular Biology : 
          To compare DNA sequences

2. File Comparison: 
3. Screen Redisplay:
           As in Mobile display only the changed pixel are updated, instead of updating the whole screen.
 This is problem is combinatorial in nature and therefore can be solved by Brute force,
Possible Subset of the given sequences of length m and n will be 2^m and 2^n respectively, which will be matched by one with each other. Thus , the Complexity of the algorithm will be exponential.

Now,
    Question is "Can we do Better" as Professor Tim Roughgarden says.


 We can see this problem fulfilling the properties of Dynamic Programming.

 Principle behind Dynamic Programming says , start with recursive algorithm , which may be inefficient because of repeated computation of sub-problems. Simply remember the solution of sub-problems, which reduce the recomputing and will be simply looked up when required.
Thus computation time reduces to proportional to the number of sub-problems.

Dynamic Programming Properties:
1. Optimal sub-structure :
           We can decompose our problem in to smaller sub-sequence and calculate solution for them.

Fig: Optimal Sub-Structure
2. Overlapping Sub-Problem:
          Our Problem involves kind of recursion.



Given

Seq 1: P R A T E E K
Seq 2: R A T H O R E


Fig: LCS for given strings
Here ,all those characters are picked which come from diagonal cell, i.e. which are marked in orange, cell in green indicates the Longest Common Sub-sequence


Full Source Code: LINK
  
 /**
  * Longest Common Sequnece Subroutine
  */
 public static int lcs(String s1, String s2){

  char[] X = s1.toCharArray();
  char[] Y = s2.toCharArray();
  int[][] LCS = new int[Y.length +1 ][X.length +1 ];

  for(int i=1;i<=Y.length;i++)
  {
   for(int j=1;j<=X.length;j++)
   {
    if(Y[i -1 ]== X[j-1])
     LCS[i][j] = 1 + LCS[i-1][j-1];
    else
     LCS[i][j] = Math.max(LCS[i-1][j], LCS[i][j-1]);
   }
  }

  // Start Trace Back
  StringBuilder sb= new StringBuilder();
  int i=Y.length ;
  int j=X.length ;

  while(i > 0 && j>0)
  {
   //System.out.println(i + " " + j);
   if(Y[i-1] == X[j-1])
   {
    sb = sb.append(X[j-1]);
    i--;
    j--;
   }
   else
   {
    if(LCS[i][j-1]> LCS[i-1][j])  
     j--;
    else
     i--;
   }
  }

  System.out.println(sb.reverse());
  return LCS[Y.length][X.length];
 }

References:1. http://www.ics.uci.edu/~eppstein/161/960229.html
                    2. Refer NPTEL videos of design and algoritms (IIT Mumbai)
                    3. http://www.youtube.com/watch?v=wJ-rP9hJXO0


Please comment  and post suggestions

Happy Coding!! :)


8 comments:

  1. Hi @Prateek; Is it possible to solve LCS in linear time..?? May be using a TRIE or.. its best we can do ie; n*m ??
    Anyways Really great blog for studying DS and algo.. ;)

    ReplyDelete
  2. There has been great increase in market research and that
    has become the sole guiding factor for all of the ways of advertising.

    Or you might simply have facts about a related field your
    target audience would find interesting. If the customer
    had to get a display, it would either need to be a one-size-fits-all model, or they could have to purchase several unique sized exhibits.


    my web page :: buy trade shows display - -

    ReplyDelete
  3. No matter the objective, ensure all people are on the same page so your design idea of the trade exhibition booth, as well as the staff working with the booth, declares a tight message to visitors.
    There could possibly be instances in which you can use spotlighting to highlight your product.
    This includes, brochures, flyers, business cards, order forms, price sheets and press kits.


    Take a look at my blog post - buy Custom Trade show displays

    ReplyDelete
  4. At the delicatessen a serve over is known to display all of the cakes
    and also other sweets and sundries which can be on offer. Or you can simply have facts about a related field that your target audience would find interesting.
    Luckily, new lead retrieval technology can address many of
    these problems.

    Also visit my web page ... inexpensive trade booth design

    ReplyDelete
  5. It's very straightforward to find out any topic on net as compared to textbooks, as I found
    this paragraph at this web site.

    my blog post ... private charter plane

    ReplyDelete
  6. Today,I went to the beach with my children. I found a seea shell and gave it
    to my 4 year old daugyhter and said "You can hear the ocean if you put this to your ear." She
    puut the shell to her eaar and screamed. There was a hermit crab inside
    and itt pinched her ear. She never wants to go back! LoL I know this is totally off topic but I had to
    tell someone!

    Feel free to surf to myy blog post :: Las Vegas Kitchen Appliance Parts

    ReplyDelete
  7. Hi there! I know this is kind of off topic but I was wondering
    if you knew where I could locate a captcha plugin for my comment form?
    I'm using the same blog platform as yours and I'm having trouble finding one?

    Thanks a lot!

    Also visit my web-site - private jet charters prices

    ReplyDelete