UNB/ CS/ David Bremner/ teaching/ cs3383/ assignments/ CS3383 Assignment 7

Dynamic programming on strings

(JE5.8) A string is palindromic if is exactly the same as its reversal, e.g. DEED, RACECAR, MURDEREDRUM. Describe and analyze an algorithm to find the length of the longest palindromic subsequence in a given string For example, the longest palindromic subsequence of MAHDYNAMICPROGRAMZLETMESHOWYOUTHEM is MHYMRORMYHM, so given that string as input, your algorithm should output the number 11.

Dynamic Programming on graphs

Based on an exercise from Jeff Erickson.

Let G = (V, E) be a directed graph with weighted edges; edge weights could be positive, negative, or zero.