[60] 1. Here, we generalize the Longest Common Subsequence (LCS) problem discussed in class to a new problem that can also be solved by dynamic programming Let be any finite alphabet containing at least two symbols. A balloon in is a subset of containing exactly two symbols. For example, if -{a, c, g,t), then {c,t) and {a,t} are balloons in , while 0, {a, c,g), and {t} are not. Note that there are ( 1) balloons in any A party over is a sequence of balloons in ; the empty party is denoted A. For example, if {a, c, g, t), is a party over of length 3. A party B-B, B2, , Bn over of length n describes a string A-, 2, ,An over of length n if B, for 1-i-n. This is written BH A. For example, an The optimization problem to be solved is: Balloon LONGEST CoMMoN SuBseQUENCE (BLCS) INSTANCE: Parties X = X1, X2, , Xm and Y-y,Y2, , Yner an alphabet SOLUTION: Strings A-2 . . .Am and B-2 . . .An such that X A. Y B, and the length of an LCS of A and B is maximurm In the subsequent steps, you are to develop a dynamic programming solution to the problem and illustrate your solution with a particular example. A. For an instance consisting of two parties X and Y, explain carefully what subinstances you identify for solution and argue that the problem possesses optimal substructure. B. Develop a recurrence for the optimal values c(i,j) for all the subinstances identified. Explain your recurrence. C. Let 2 - {a, c, g,t}. Write a small program in your favorite programming language to generate a random party over of length n. Include the code for your program in your solution. Generate an example random party X = Xi,X2,Xy, X4,Xs, X6,Xy of length 7 and an example random party Y = Yi, ,Yo, Y4,Ys of length 5. D. Figure 1 gives the template for the table to contain the results of dynamic programming on the BLCS instance (X, Y) from Item C. Fill in the table with the c(i, j) values obtained from your recurrence. Include the arrows1, as was done in the example of LCS in class. What is the optimal objective value for the instance (X.Y)? Xi 1 X3 3 X5 5 X7 7 Figure 1: Table template for dynamic programming solution of BLCS instance E. Use backtracing to obtain A and B such that X- A, Y- B, and A and IB have a longest possible LCS. Especially show the arrows2 in the table that are part of finding A and B. What are the A and B you obtain? [60] 1. Here, we generalize the Longest Common Subsequence (LCS) problem discussed in class to a new problem that can also be solved by dynamic programming Let be any finite alphabet containing at least two symbols. A balloon in is a subset of containing exactly two symbols. For example, if -{a, c, g,t), then {c,t) and {a,t} are balloons in , while 0, {a, c,g), and {t} are not. Note that there are ( 1) balloons in any A party over is a sequence of balloons in ; the empty party is denoted A. For example, if {a, c, g, t), is a party over of length 3. A party B-B, B2, , Bn over of length n describes a string A-, 2, ,An over of length n if B, for 1-i-n. This is written BH A. For example, an The optimization problem to be solved is: Balloon LONGEST CoMMoN SuBseQUENCE (BLCS) INSTANCE: Parties X = X1, X2, , Xm and Y-y,Y2, , Yner an alphabet SOLUTION: Strings A-2 . . .Am and B-2 . . .An such that X A. Y B, and the length of an LCS of A and B is maximurm In the subsequent steps, you are to develop a dynamic programming solution to the problem and illustrate your solution with a particular example. A. For an instance consisting of two parties X and Y, explain carefully what subinstances you identify for solution and argue that the problem possesses optimal substructure. B. Develop a recurrence for the optimal values c(i,j) for all the subinstances identified. Explain your recurrence. C. Let 2 - {a, c, g,t}. Write a small program in your favorite programming language to generate a random party over of length n. Include the code for your program in your solution. Generate an example random party X = Xi,X2,Xy, X4,Xs, X6,Xy of length 7 and an example random party Y = Yi, ,Yo, Y4,Ys of length 5. D. Figure 1 gives the template for the table to contain the results of dynamic programming on the BLCS instance (X, Y) from Item C. Fill in the table with the c(i, j) values obtained from your recurrence. Include the arrows1, as was done in the example of LCS in class. What is the optimal objective value for the instance (X.Y)? Xi 1 X3 3 X5 5 X7 7 Figure 1: Table template for dynamic programming solution of BLCS instance E. Use backtracing to obtain A and B such that X- A, Y- B, and A and IB have a longest possible LCS. Especially show the arrows2 in the table that are part of finding A and B. What are the A and B you obtain