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.

• Describe an algorithm that constructs a directed graph ```H = (V' , E' )``` with weighted edges, where `V' = V ∖ {v}`, and the shortest-path distance between any two nodes in `H` is equal to the shortest-path distance between the same two nodes in `G`, in `O(|V|²)` time.

• Now suppose you know all shortest-path distances in `H` . Describe an algorithm to compute the shortest-path distances from `v` to every other node, and from every other node to `v`, in the original graph `G`, in `O(|V|²)` time.

• Combine the above results into an all-pairs shortest path algorithm that runs in `O(|V|³)` time. (The resulting algorithm is not the same as Floyd-Warshall!)