Tuesday, January 9, 2018

Subsequence Problems


What is subsequences ?


In mathematics, a subsequence is a sequence that can be derived from another sequence by deleting some elements without changing the order of the remaining elements



For example, the sequence  is a subsequence of  obtained after removal of elements , and . The relation of one sequence being the subsequence of another is a preorder.

The subsequence should not be confused with substring  which can be derived from the above string  by deleting substring . The substring is a refinement of the subsequence.
The list of all subsequences for the word "apple" would be "e, l, le, p, pe, pl, ple, p, pe, pl, ple, pp, ppe, ppl, pple, a, ae, al, ale, ap, ape, apl, aple, ap, ape, apl, aple, app, appe, appl, apple".

Problem 1 

Kadane's algorithm: 
finds maximum sub-array of any size

Problem  2

 Longest common subsequence problem: 

Find the longest subsequence common to all sequences in a set of sequences










Problem 3

Longest increasing subsequence problem: Find the longest increasing subsequence of a given sequence

Problem  4

Longest palindrome subsequence : 

Find the longest increasing subsequence of a given sequence











Problem 5



Longest palindrome substring :  (MANCHESTER'S ALGORITHMS)

Find the longest palindrome substring of a given sequence








Problem 5


 Shortest common supersequence problem: Find the shortest supersequence that contains two or more sequences as subsequences

No comments:

Post a Comment