algorithm

2. [10pts] Consider the Shortest common super-sequence(SCS) of two sequences A and B, which is the shortest sequence C such that both A and B are subsequences of C. Design an algorithm that finds the SCS(A,B). 3. [10pts] Given the keys k1,k2,k3,k4,k5 sorted in ascending order alphabetically, with respective search frequencies of 0.30,0.04,0.01,0.45,0.20, construct the optimum binary search tree and write down its cost. 23 at 5.30pm. The submissions must be done through LMS as a single .pdf file. 1. Consider the longest common subsequence (LCS) problem defined on two strings A,B, with lengths n,m, respectively. (a) Provide a recurrence defining the cost. (b) [10pts] Provide the cost table for the LCS of the strings A="010101" and B= "1011011