5. (10 pts) A palindrome is any string that is exactly the same as its reversal,

Question

5. (10 pts) A palindrome is any string that is exactly the same as its reversal, like I, or DEED, or RACECAR, or AMANAPLANACANALPANAMA. For example, in sequence MAHDYNAMICPROGRAMZLETMESHOWYOUTHEM, the longest subsequence that is a palindrome is MHYMRORMYHM, so given that string as input, your algorithm should output the number 11. (a) (7 pts) Describe in pseudo-code an o(72) time algorithm to find the length of the longest subsequence of a given string that is also a palindrome. The key is to find a recursive description of the optimal solution in terms of the optimal solution of smaller subproblems. If you are unable to find an o(72) time algorithm, then for part marks, you can give an o(n) or O(n) time algorithm (b) (3 pts) Analyze the running time of your algorithm.

Explanation / Answer

A palindrome is any string that is exactly the same as reversal.

In sequence MAHDYNAMICPROGRAMZLETMESHOWYOUTHEM, the longest subsequence that is palindrome is MHYMRORMTHM. The length of the subsequence is 11.

1) Optimal Substructure:

Following is a general recursive solution with all cases handled.

// Every single character is a palindrom of length 1

2) Overlapping Subproblems

following is a partial recursion tree for a sequence of length 5 with all different characters.

(0,4)

(1,4) (0,3)

(2,4) (1,3) (1,3) (0,2)

As you can see that the subproblem (1,3) is repeating ,i.e both Optimal Substructure and Overlapping Subproblems (Dynamic Problem it is).

For the dynamic problem solution,

1.int L[n][n]; // Create a table to store results of subproblems ,n is the size of the String

2. Strings of length 1 are palindrome of length 1

3. Build the table. Note that the lower diagonal values of table are useless and not filled in the process.

The running time complexity is O(n2), as we can see through the algorithm.

Related Questions

Navigate

• Browse (All)
• Browse 5
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.