[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 are balloons in , while , {a, c,g), and {t} are not. Note that there are (1,1) balloons in A party over is a sequence of balloons in ; the empty party is denoted A. For example, if -a, c,g,t) (c,ty,(a,t,ta,g 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 ifai E Bi, for 1 i n. This is written B A. For example, and The optimization problem to be solved is BALLOON LONGEST COMMON SUBSEQUENCE (BLCS) INSTANCE: Parties X = X1, X2, . . . , Xm and Y Y, 2, , Y,, over an alphabet 2. SOLUTION: Strings A a1am and B B1B2 Bn such that XF A, Y H B, and the length of an LCS of A and B is maximum. 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 recur rence. C. Let a, c,g,t). Write a smal 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 XX1, X2, X3, X4, X5, X6, X7 of length 7 and an example random party Y-Y, YS, Ya, 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. Fil in the table with the c(i. j) values obtained from your recurrence. Include the arrows', as was done in the example of LCS in class. What is the optimal objective value for the instance (X, Y)? c(i.j)012 i X4 4 X7 7 Figure 1: Table template for dynamic programming solution of BLCS instance E. Use backtracing to obtain A and B such that XHA,Y B, and A and B have a longest possible LCS. Especially show the arrows 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 are balloons in , while , {a, c,g), and {t} are not. Note that there are (1,1) balloons in A party over is a sequence of balloons in ; the empty party is denoted A. For example, if -a, c,g,t) (c,ty,(a,t,ta,g 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 ifai E Bi, for 1 i n. This is written B A. For example, and The optimization problem to be solved is BALLOON LONGEST COMMON SUBSEQUENCE (BLCS) INSTANCE: Parties X = X1, X2, . . . , Xm and Y Y, 2, , Y,, over an alphabet 2. SOLUTION: Strings A a1am and B B1B2 Bn such that XF A, Y H B, and the length of an LCS of A and B is maximum. 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 recur rence. C. Let a, c,g,t). Write a smal 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 XX1, X2, X3, X4, X5, X6, X7 of length 7 and an example random party Y-Y, YS, Ya, 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. Fil in the table with the c(i. j) values obtained from your recurrence. Include the arrows', as was done in the example of LCS in class. What is the optimal objective value for the instance (X, Y)? c(i.j)012 i X4 4 X7 7 Figure 1: Table template for dynamic programming solution of BLCS instance E. Use backtracing to obtain A and B such that XHA,Y B, and A and B have a longest possible LCS. Especially show the arrows in the table that are part of finding A and B. What are the A and B you obtain