Furthermore, please note that the graders will grade 2 out of the 4 questions randomly. Therefore, if the grader decides to check questions 1 and 4,and you haven’t answered question 4, you’ll lose points for question 4. Hence, please answer all the questions.
1. Find the optimal order of multiplying four matrices whose sequence ofdimensions are [13,5,89,3,34] (i.e. the first matrix is 13 × 5, the second matrix is 5 × 89, and so on) and also the fewest number of multiplications needed to find the resulting matrix. Do it using the Matrix chain multiplication formulation we discussed in class. Show all the steps of computation and all your work. [25 points]
2. Find the longest common subsequence(as described in class and the slides) of the following two sequences by Dynamic Programming Algorithm. X = ABCBDAB , Y= BDCABA Show all your work. [25 points]
3. Given three strings S1, S2 and S3. S1 and S2 are signals emitted by twoships and S3 is the string which the receiver gets. You want to check if the String S3 is an interleaving of the strings S1 and S2. Write a function that checks if S3 is an interleaving of strings S1 and S2.
For three strings A, B, and C, C is said to be interleaving A and B, if it contains all and only characters of A and B and order of all characters in individual strings is preserved. For example if A = aabcc and B = dbbca and C = aadbbcbcac. We can say C is an interleaving string of A and B as A = aa+bc+c and B = dbbc+a. Now we can get C as aa+dbbc+bc+a+c. [10 + 15 points]
• Given three strings S1, S2 and S3 give the dynamic programming framework (DP formulation) to check if S3 is an interleaving string
1
of S1 and S2. For three strings we need to result True if S3 is an interleaving string of S1 and S2, false otherwise.
• Write pseudo-code for a polynomial time algorithm which takes S1, S2, and S3 as arguments and returns true if S3 is an interleaving string of S1 and S2, false otherwise.
4. Given a string S, find the length of the longest palindromic subsequenceof the string S. Refer to subsequence definition discussed in class. A string P is a palindrome if it is reads the same from front and back. [10 + 15 points]
• Given a string S, give the dynamic programming framework (DP formulation) to find the length of longest palindromic subsequence of S.
• Write pseudo-code for a polynomial time algorithm which takes S, and returns the length of its longest palindromic subsequence.
2
