1.Consider a set of keys K1 < K2 < < Kn. Let pi for 1 ? i ? n denote the probability of searching for key Ki and qi for 0 ? i ? n denote the probability of searching for a key Ei where ai < Ei < ai+1, a0 = ??, and an+1 = +?. Let T(i, j) denote an optimal binary search tree containing Ei , ai+1, Ei+1, , aj , Ej . Let C(i, j) and R(i, j) denote the cost (i.e., the average number of comparisons to search for a key) and the root of T(i, j). Define W(i, j) = qi + pi+1 + qi+1 + pj + qj .

(a) Describe a dynamic programming algorithm to construct an optimal binary search tree.

(b) Consider the following example: a1 < a2 with q0 = 2/10, p1 = 1/10, q1 = 3/10, p2 = 3/10, and q2 = 1/10. Apply your algorithm in (a) to compute C(i, j) and R(i, j), and construct an OBST for this example. Show all your steps.

2.Given two strings X and Y , respectively, of length m and n defined over a set ? = {a1, a2, , ak} of finitely many symbols, we are interested in computing an optimal (i.e., minimum cost) alignment of two strings, where two possible alignments are defined as (i) a mismatch with cost cm and (ii) a gap with cost dg. Consider the following two sequences defined over ? = {A, G, C, T}, where X = {A A C A G T T A C C} and Y = {T A A G G T C A} In the following alignment, there are two mismatches and four gaps with total cost 2cm + 4cg: {? A A C A G T T A C C} and {T A A ? G G T ? ? C A}. Give an dynamic programming algorithm to solve this problem.