Let A[1..m] and B[1..n] be two arrays. Each of the following problems asks for some aspect...

  

Transcribed Image Text:

Let A[1..m] and B[1..n] be two arrays. Each of the following problems asks for some aspect (e.g., the length) of a common subsequence of A[1..n] and B[1..n] satisfying or optimizing certain properties. (A common subsequence of A and B is a sequence that is a subsequence of both A and B.) Design and analyze an algorithm for each of these problems, addressing items 1-5 from section 11.1.3.10 1. Compute the length of the longest common subsequence of A and B. 2. Compute the length of the shortest common supersequence of A and B. 3. Compute the length of the longest common subsequence of A and B that is a palindrome. 4. Suppose A and B consists of integers. Compute the length of the longest common increasing subsequence of A and B. 5. Compute the length of the shortest common palindrome supersequence of A and B. Activate Windows Go to Settings to activate Let A[1..m] and B[1..n] be two arrays. Each of the following problems asks for some aspect (e.g., the length) of a common subsequence of A[1..n] and B[1..n] satisfying or optimizing certain properties. (A common subsequence of A and B is a sequence that is a subsequence of both A and B.) Design and analyze an algorithm for each of these problems, addressing items 1-5 from section 11.1.3.10 1. Compute the length of the longest common subsequence of A and B. 2. Compute the length of the shortest common supersequence of A and B. 3. Compute the length of the longest common subsequence of A and B that is a palindrome. 4. Suppose A and B consists of integers. Compute the length of the longest common increasing subsequence of A and B. 5. Compute the length of the shortest common palindrome supersequence of A and B. Activate Windows Go to Settings to activate