Results 1 to 2 of 2
Like Tree1Thanks
  • 1 Post By SlipEternal

Math Help - An efficient algorithm that finds subsequences?

  1. #1
    Newbie
    Joined
    Oct 2013
    From
    Oregon
    Posts
    3

    An efficient algorithm that finds subsequences?

    Can anyone help me come up with a solution to this problem I found in my textbook please?

    imgur: the simple image sharer


    Thanks!
    Attached Thumbnails Attached Thumbnails An efficient algorithm that finds subsequences?-577_3-2.jpg  
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Nov 2010
    Posts
    1,930
    Thanks
    782

    Re: An efficient algorithm that finds subsequences?

    Start with any algorithm that gives the correct answer. Figure out where inefficiency arises and alter the algorithm to reduce it. Depending on the definition your book gives for "efficient", this may require several attempts until you get an efficient algorithm.

    Example: If the length of a is smaller than the length of b, have the algorithm return the result when the sequences are swapped. Then, find the longest subsequence of a that is also a subsequence of b. Then, proceed to add digits to the sequence a until b is a subsequence in its entirety.

    This algorithm is not well defined, but it gives a basic idea of the process. It is probably extremely inefficient, since finding the longest subsequence of a that is also a subsequence of b requires checking all possible subsequences of one of the two and comparing it to the other.
    Thanks from Shakarri
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Efficient algorithm
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: December 25th 2012, 02:18 AM
  2. Subsequences
    Posted in the Differential Geometry Forum
    Replies: 2
    Last Post: August 19th 2011, 08:28 AM
  3. how the Calculator finds definite Integrals?
    Posted in the Calculators Forum
    Replies: 1
    Last Post: September 7th 2009, 05:59 AM
  4. subsequences
    Posted in the Calculus Forum
    Replies: 1
    Last Post: October 10th 2008, 09:17 AM
  5. [SOLVED] Subsequences help, please!
    Posted in the Calculus Forum
    Replies: 1
    Last Post: November 13th 2007, 11:35 AM

Search Tags


/mathhelpforum @mathhelpforum