CSCI 570 - HW 7
Question 1
Suppose you have a DAG with costs ce 0 on each edge and a distinguished vertex s. Give
a dynamic programming algorithm to find the most expensive path in the graph that begins
at s. Prove your algorithm’s runtime and correctness. For full credit, your algorithm’s
runtime should be linear.
Question 2
A palindrome is a string that reads the same forwards and backwards. Suppose we are given
a string S = s1s2s3...sn, and we want to find the longest palindrome that can be formed by
deleting some characters from the string. Give an efficient dynamic programming algorithm
to solve this problem. Prove its running time and correctness. For full credit, your algorithm
should output which character(s) to delete to form the longest palindrome.
Question 3
Suppose you are in Casino with your friend, and you are interested in playing a game
against your friend by alternating turns. The game contains a row of n coins of values v(i),
where n is even. In each turn, a player selects either the first or last coin from the row,
removes it from the row permanently, and receives the value of the coin. Determine the
maximum possible amount of money you can definitely win if you move first.
Question 4
Given a rod of length n inches and an array of prices that contains prices of all pieces of
size smaller than n. Determine the maximum value obtainable by cutting up the rod and
selling the pieces.
