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!)