Question

A palindrome is a string of characters that is the same when reversed (e.g., ‘affa’). Single characters are palindromes. Suppose you are given a string S of N characters and wish to produce an N-by-N matrix P, where P = 1 if i ≤ j and S[i,...,j] is a palindrome, and Pij = 0 otherwise.
(A) Matrix P can be computed using brute force by separately examining each substring of S and determining whether it is a palindrome. Describe this algorithm. What is the algorithm’s running time?
(B) It is possible to compute matrix P more efficiently using dynamic programming. Give a dynamic programming algorithm to compute P, and analyze its running time. (Hint: Begin by filling in the values along the diagonal of the matrix.)

Answer 1

Answer:

Check the explanation

Explanation:

a) This done can be executed through the use of brute force by the given algorithm: Consider any two indices i and j then we can check if string from s[i....j] is palindrome or not in O(L) where L is length of string.

Algorithm to check if string is palindrome :

Takes String s as argument and the two indices i,j between which the string is to be considered

bool palindromeCheck(s,i,j) :

        y = j

        for x in range(i,j) :

             if(s[x]==s[y]) :

                      y--

                      continue

            else :

                      return false

       return true

Now taking a look at the  part a) we will be calling the function to confirm and execute palindrome for all i<=j that is a total of points of the order of O(n^2) and the string checking will take O(n) in the worst case making it O(n^3).

b) To advance over we became aware of the fact that repeated calculation is being done i.e when we confirmed the string s[i...j] we also tested in between strings like s[i+1,j-1] etc in the same time. Consequently we used memorization to store the outcome that we calculate and reuse them we need them later.

We know that P[i][i] will always be one since a single character string will always be a palindrome.

Using this as our base case to check for P[i][j] we need to check if the ith and the jth character are equal and also if P[i+1][j-1] is true i.e is a palindrome.

We come up with the following recurrence

P[i][j] = 1 if i=j

P[i][j] = P[i+1][j-1] ; if i>=j and s[i]==s[j]

            0; otherwise

There are order of O(n^2) states and each one of the state necessitates only constant and regular time character checking for its evaluation and then assigning the value of 1, P[i+1][j-1],0 as a result of that which is again a constant time operation. Therefore all the P[][] matrix values can be found in O(n^2) time.

Pseudo code :

Let n be the length of the string

for x in range(1,n) :

        P[x][x]=1

for sz in range(2,n) : # Since we have already computed answer for string of size 1

        for x in range (1,n-sz+1):

                   y=x+sz - 1

                   if x == y :

                            if sz==2 :

                                      P[x][y] = 1

                            else :

                                      P[x][y] = P[x+1][y-1]

                  else :

                            P[x][y] = 0

From the implementation also it is clear that the running time of the algorithm is O(n^2).