Historie

1. Step 1 of 4

   The given string in the table is examined and the efficient way to carry out this algorithm is determined by dynamic programming.

   Sub-problems:

   Consider, be the original string in the order they appear.

   Let = set of all possible values of the substring under all the ways of parenthesizing for.

   • If the value, then the algorithm returns “True” for the input.

   • Else the algorithm returns “False”.

   By the dynamic programming definition, is the set of all possible values of the under all the ways of parenthesization, if the output “a” belongs to the set, then there exists a way to parenthesize “S”, which is considered as the input expression that gives the value “a”.

   Recursion:

   • The answer figured out using the sub-problems is correct, because the set of possible characters are computed and obtained using all the ways of parenthesization of the string.

   • The variable “j” of the substring is used to indicate the position where the string is separated.

   • Since, by considering all intermediate positions of “j” where the expression is splitting into two products we can compute the result by taking union of the products.

   

   Proof for correctness:

   The proof of correctness follows from the correctness of the recurrence.

   Proof by induction:

   Base case:

   The base case template states that, “one or more particular cases are used to represent the most basic case”. The base cases are:

   For the value ,

   • Then there is only one character all possible values of the should be considered which is.

   • If is true then the value of , otherwise it is false.

   • If is true then the value of , otherwise it is false.

   For the value of ,

   • If the substring is longer than one character, then is true, if can be split into two parts.

   Pseudo code:

   // Matrix to store the values of L

   L(n,n,3)

   // Read the values from 1 to n of i

   for i from 1 to n:

   // Read the values from 1 to n of j

   for j from 1 to n:

   // Read the values from a,b,c of j

   for k from {a,b,c}:

   // Condition to check the values

   if (i==j and p[i]==k):

   // Assign the value of matrix as 1

   L(i,j,k) = 1

   else:

   // Assign the value of matrix as -1

   L(i,j,k) = -1

   // End the condition

   end if

   // End for loop

   end for

   // End for loop

   end for

   // End for loop

   end for

   // Function definition

   function true(i,j,m)

   // Condition to check the values of matrix

   if (L(i,j,m) != -1)

   // Return the value in matrix

   return L(i,j,m)

   Comment
2. Step 2 of 4

   else:

   // Read the values from i to j of x

   for x from i to j:

   // Read the values a,b,c of y

   for y from {a,b,c}

   // Read the values a,b,c of z

   for z from {a,b,c}

   // Condition to check the values

   if (true(i,y,z)* true(x+1,j,z)==1 and yz == a)

   // Assign the value of matrix as 1

   L(i,j,m) = 1

   else:

   // Assign the value of matrix as 1

   L(i,j,m) = 0

   // End the condition

   end if

   // End for loop

   end for

   // End for loop

   end for

   // End for loop

   end for

   // End the condition

   end if

   // Return the value of the matrix

   return L(1,n,a)

   Comment
3. Step 3 of 4

   Correctness and Running time:

   • The computation of the algorithm is done as bottom up.

   • The computation starts at

   • We need previously computed values of the sub-problems to solve the next sub-problem. Hence, to compute we need previously computed values of L function.

   • Each sub-problem takes time of.

   • We have sub-problem to be computed.

   Therefore, the total running time of the algorithm is .

   Comment
4. Step 4 of 4

   Example:

   • Using the string “bbbbac”, the above algorithm is performed here:

   Calculation:

   

   Using the above calculation, the remaining values in the matrix are calculated.

   

   Comment