Results 1 to 5 of 5

Math Help - Algorithms!

  1. #1
    Member
    Joined
    May 2006
    Posts
    148
    Thanks
    1

    Algorithms!

    Hello; I have this question regarding an algorithm. CaptainBlack, in particular, if you have some time mind giving it a shot, as last time you were able to help me with another algorithm. Thanks!

    "22.7 Maximal palindromes

    A palindrome is a string that reads the same forwards as backwards, such as axbccbxa.A substring U of a string S is a maximal palindrome if and only if it is a palindrome and extending it onecharacter in both directions yields a string that is not a palindrome. Generally we separate even-length maximalpalindromes, or even palindromes for short, and odd-length maximal palindromes (odd palindromes) for convenience. For example, in S = axbccbbbaa, the maximal even palindromes are bccb,bb, and aa. The string bbb isa maximal odd palindrome, and we will skip writing the maximal odd palindromes of length 1. Note that everypalindrome is contained in a maximal palindrome.

    (Below is an algorithm for finding the even-length palindromes of S; suppose length of S= n).

    Here is a simple way to find all even-length maximal palindromes in linear time. (Finding odd-length maximal palindromes is similar.)

    Consider S$ and S^r#, the reversal of S. There is a palindrome of length 2k with the middle just after position q ifthe string of length k starting from position q+1 of S matches the string of length k starting from position n−q+1of S^r#. In particular, this palindrome will be maximal if this is the length of the longest match from these positions.Thus, solving the even-length maximal palindrome problem corresponds to computing the longest commonextension of (q+1,n−q+1) for all possible q."

    QUESTIONS:

    1.) How do we change the above algorithm so that it finds odd-length palindromes?

    2.) Using both the even algorithm and the one you come up with in 1, find all of the even and odd palindromes of the following string: c b a a b a

    3.) Consider MISSISSIPPI$ and IPPISSISSIM#; if we were to run both of the algorithms, list each of the q's and the palindrome(s) that we'd get for that q. (Note: we may not get any palindromes for a specific q, if so then say 'none'.

    4.) In fact, we do not get all palindromes of a string. What type of palindromes do we end up getting?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by fifthrapiers View Post
    Hello; I have this question regarding an algorithm. CaptainBlack, in particular, if you have some time mind giving it a shot, as last time you were able to help me with another algorithm. Thanks!

    "22.7 Maximal palindromes

    A palindrome is a string that reads the same forwards as backwards, such as axbccbxa.A substring U of a string S is a maximal palindrome if and only if it is a palindrome and extending it onecharacter in both directions yields a string that is not a palindrome. Generally we separate even-length maximalpalindromes, or even palindromes for short, and odd-length maximal palindromes (odd palindromes) for convenience. For example, in S = axbccbbbaa, the maximal even palindromes are bccb,bb, and aa. The string bbb isa maximal odd palindrome, and we will skip writing the maximal odd palindromes of length 1. Note that everypalindrome is contained in a maximal palindrome.

    (Below is an algorithm for finding the even-length palindromes of S; suppose length of S= n).

    Here is a simple way to find all even-length maximal palindromes in linear time. (Finding odd-length maximal palindromes is similar.)

    Consider S$ and S^r#, the reversal of S. There is a palindrome of length 2k with the middle just after position q ifthe string of length k starting from position q+1 of S matches the string of length k starting from position n−q+1of S^r#. In particular, this palindrome will be maximal if this is the length of the longest match from these positions.Thus, solving the even-length maximal palindrome problem corresponds to computing the longest commonextension of (q+1,n−q+1) for all possible q."

    QUESTIONS:

    1.) How do we change the above algorithm so that it finds odd-length palindromes?
    This should do the job (though messing with these indicies is tricky).

    Consider S$ and S^r#, the reversal of S. There is a palindrome of length 2k+1 with the middle at position q if the string of length k starting from position q+1 of S matches the string of length k starting from position n−q+2of S^r#.

    RonL

    (note: my first go at this had to be modified in the light of what the actual code
    did, when I cam to run it)
    Last edited by CaptainBlack; December 15th 2006 at 03:13 AM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by fifthrapiers View Post
    2.) Using both the even algorithm and the one you come up with in 1, find all of the even and odd palindromes of the following string: c b a a b a
    The following functions implement the algorithms (as far as I can tell)
    (note I am working with numerical arrays rather than strings as it is
    easier to implement quickly)

    (code written so quickly comes with no guarantee of correctness )

    Code:
    function Epalind(s)
    ##
    ##  find even palindromes in s
    ##
    ##
      n=length(s);
      sr=s(n:-1:1);
      for q=1 to n
        mxk=min(n-q,q-1);
        for k=1 to mxk
          s1=s(q+1:q+k);
          s2=sr(n-q+1:n-q+k);
          if prod(s1==s2)==1
            s(q-k+1:q+k)
          endif
        end
      end
      return 0
    endfunction
     
    ..======================================
     
    function Opalind(s)
    ##
    ##  fid odd palindromes in s
    ##
      n=length(s);
      sr=s(n:-1:1);
      for q=1 to n
        mxk=min(n-q,q-1);
        for k=1 to mxk
          s1=s(q+1:q+k);
          s2=sr(n-q+2:n-q+k+1);
          if prod(s1==s2)==1
            s(q-k:q+k)
          endif
        end
      end
      return 0
    endfunction
    Results are:

    Code:
     
    >
    >s=[3,2,1,1,2,1];
    >Epalind(s);
                1             1 
                2             1             1             2 
    >
    >
    >Opalind(s);
                1             2             1 
    >
    RonL
    Last edited by CaptainBlack; December 15th 2006 at 03:14 AM.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by fifthrapiers View Post
    3.) Consider MISSISSIPPI$ and IPPISSISSIM#; if we were to run both of the algorithms, list each of the q's and the palindrome(s) that we'd get for that q. (Note: we may not get any palindromes for a specific q, if so then say 'none'.

    Not quite theformat the question asks for (code modified to print
    q and k):

    Code:
     
    >s=[13,9,19,19,9,19,19,9,16,16,9];
    >
    >
    >Epalind(s)
    q= 3    k= 1
      19   19 
     
    q= 3    k= 2
       9   19   19    9 
     
    q= 6    k= 1
      19   19 
     
    q= 6    k= 2
       9   19   19    9 
     
    q= 9    k= 1
      16   16 
     
    q= 9    k= 2
       9   16   16    9 
     
       0 
    >Opalind(s);
    q= 5    k= 1
      19    9   19 
     
    q= 5    k= 2
      19   19    9   19   19 
     
    q= 5    k= 3
       9   19   19    9   19   19    9 
     
    >
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by fifthrapiers View Post
    4.) In fact, we do not get all palindromes of a string. What type of palindromes do we end up getting?
    It might be a bug, but I dont pick up where the length of S is even and
    S is a palindrome itself.

    RonL
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Algorithms
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: October 8th 2010, 09:48 PM
  2. algorithms
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: March 16th 2010, 02:25 PM
  3. Algorithms
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: December 17th 2009, 07:11 AM
  4. Algorithms
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: December 4th 2009, 03:06 AM
  5. Algorithms
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: March 4th 2009, 11:33 AM

Search Tags


/mathhelpforum @mathhelpforum