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

**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!! :)**

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

ReplyDeleteAnyways Really great blog for studying DS and algo.. ;)

There has been great increase in market research and that

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

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.

ReplyDeleteThere 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

At the delicatessen a serve over is known to display all of the cakes

ReplyDeleteand 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

It's very straightforward to find out any topic on net as compared to textbooks, as I found

ReplyDeletethis paragraph at this web site.

my blog post ... private charter plane

Today,I went to the beach with my children. I found a seea shell and gave it

ReplyDeleteto 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

Hi there! I know this is kind of off topic but I was wondering

ReplyDeleteif 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