P1) Consider the problem of finding the shortest common super-sequence of three strings

*A*,

*B*, and

*C*. Try to find an efficient dynamic programming algorithm for this problem. What, if anything, makes this difficult?

P2) The input for this problem consists of

*n*keys <!-- MATH

$K_1, \ldots, K_n$

-->[img]file:///C:/Documents%20and%20Settings/Le%20Huy%20Cuong/Desktop/Cong%20Viec/Cao%20hoc%202004/Ly%20thuyet%20tinh%20toan/Mot%20so%20BT%20va%20LG/dynproghomeworks_files/img7.gif[/img], with <!-- MATH

$K_1 < K_2 < \ldots, K_n$

-->[img]file:///C:/Documents%20and%20Settings/Le%20Huy%20Cuong/Desktop/Cong%20Viec/Cao%20hoc%202004/Ly%20thuyet%20tinh%20toan/Mot%20so%20BT%20va%20LG/dynproghomeworks_files/img8.gif[/img], and associated probabilities <!-- MATH

$p_1, \ldots, p_n$

-->[img]file:///C:/Documents%20and%20Settings/Le%20Huy%20Cuong/Desktop/Cong%20Viec/Cao%20hoc%202004/Ly%20thuyet%20tinh%20toan/Mot%20so%20BT%20va%20LG/dynproghomeworks_files/img9.gif[/img]. The problem is to find the AVL tree for these keys that minimizes the expected depth of a key. An AVL tree is a binary search tree with the property that every node has balance factor -1, 0, or 1. Give a polynomial time algorithm for this problem.

HINT: You will have to strengthen the inductive hypothesis. Obviously the height of a subtree is relevant

P3) The input consists of

*n*intervals over the real line. The output should be a collection

*C*of non-overlapping intervals such the sum of the lengths of the intervals in

*C*is maximized. Give a polynomial time algorithm for this problem.

HINT: Strengthen the induction hypothesis. Consider the intervals by increasing order of their left endpoints. Just like in the Longest Increasing Subsequence (LIS) problem, there are two pieces of information that are relevant about a partial solution. One is obviously the length of the intervals, what is the other? Think about what the answer was in the LIS problem.