Question

In: Computer Science

Build a Dynamic Programming algorithm in Python for the following problem. Given two sequences of vowels,...

Build a Dynamic Programming algorithm in Python for the following problem.

Given two sequences of vowels, find the length of longest subsequence present in both of them.

NOTE: A subsequence is a sequence that appears in the same order, but not necessarily contiguous. For example, “aei”, “aeo”, “eio”, “aiu”, ... are subsequences of “aeiou”.

Sample Input 1:

aeiou aiu

Sample Output 1:

3

Sample Input 2:

aeaiueoiuaeeoeooaauoi aeuioauuuoaeieeaueuiouaiieuiuuuaoueueauaeiauuo

Sample Output 2:

16

Sample Input 3:

iioioieiaiauaoeoiioiiue iuuueauiaieooaoaaouaaaae

Sample Output 3:

10

Sample Input 4:

iauuieeuuiieiuaeaioaieiaeeuouueaeiuiuuaiioaeuoueuiue oeeiauiiioaieoaouuuiueouauueeiauuiiuueeo

Sample Output 4:

26

Write a program, test using stdin → stdout

Solutions

Expert Solution

def longest_subsequence(first, second, len_1, len_2):

    # if current longest is not computed till now

    if table[len_1][len_2] == None:

        # compute current longest

        if len_1 == 0 or len_2 == 0:

            longest = 0

        # both characters are same

        elif first[len_1-1] == second[len_2-1]:

            longest = 1 + longest_subsequence(first, second, len_1-1, len_2-1)

        # both characters are different

        else:

            # compute longest subsequence by first taking first element, then second element

            temp_1 = longest_subsequence(first, second, len_1, len_2-1)

            temp_2 = longest_subsequence(first, second, len_1-1, len_2)

            # longest will be maximum of both of above

            longest = max(temp_1, temp_2)

        # store current longest

        table[len_1][len_2] = longest

    # return longest subsequence

    return table[len_1][len_2]


# read 2 strings of vowels

first, second = input().split()

len_1 = len(first)

len_2 = len(second)

# matrix table for dynamic programming

table = [[None]*(len_2+1) for i in range(len_1+1)]

# print longest common subsequence

print(longest_subsequence(first, second, len_1, len_2))

.

Screenshot:

.

Output:

.


Related Solutions

5. Design a dynamic programming algorithm to solve the following problem. Input: An array A[1, ....
5. Design a dynamic programming algorithm to solve the following problem. Input: An array A[1, . . . , n] of positive integers, an integer K. Decide: Are there integers in A such that their sum is K. (Return T RUE or F ALSE) Example: The answer is TRUE for the array A = [1, 2, 3] and 5, since 2 + 3 = 5. The answer is FALSE for A = [2, 3, 4] and 8. Note that you...
Problem 2. Purpose: practice algorithm design using dynamic programming. A subsequence is palindromic if it is...
Problem 2. Purpose: practice algorithm design using dynamic programming. A subsequence is palindromic if it is the same whether read left to right or right to left. For instance, the sequence A,C,G,T,G,T,C,A,A,A,A,T,C,G has many palindromic subsequences, including A,C,G,C,A and A,A,A,A (on the other hand, the subsequence A,C,T is not palindromic). Assume you are given a sequence x[1...n] of characters. Denote L(i,j) the length of the longest palindrome in the substring x[i,...,j]. The goal of the Maximum Palindromic Subsequence Problem (MPSP)...
Recall the dynamic programming algorithm we saw in class for solving the 0/1 knapsack problem for...
Recall the dynamic programming algorithm we saw in class for solving the 0/1 knapsack problem for n objects with a knapsack capacity of K. In particular, we characterized our recurrence OPT(j, W) to be following quantity: OPT(j, W) := The maximum profit that can be obtained when selecting from objects 1, 2, . . . , j with a knapsack capacity of W , where (after filling in our dynamic programming table), we return the value stored at OPT(n, K)...
Show that the worst-case number of entries computed by the refined dynamic programming algorithm for the...
Show that the worst-case number of entries computed by the refined dynamic programming algorithm for the 0-1 Knapsack problem is in Ω(2n). Do this by considering the instance in which W = 2n −2 and wi = 2i−1 for 1 ≤ i ≤ n. Please answer with clear explanations!!! Excerpt From: Richard Neapolitan. “Foundations of Algorithms.”
What is the auxiliary space and space complexity for a dynamic programming algorithm with time complexity...
What is the auxiliary space and space complexity for a dynamic programming algorithm with time complexity of O(n^2)? Justify.
Implement Radix Sort using PYTHON programming language. Use one of the two options for the algorithm...
Implement Radix Sort using PYTHON programming language. Use one of the two options for the algorithm to sort the digits: Use Counting Sort or Bucket Sort. • Assume the numbers are maximum 4-digit numbers. • If using Counting Sort, you can see that your digit range is between 0 and 9 ([0…9]). • If using Bucket Sort, you will have ten buckets labeled from 0 to 9. Please add comments and explain every step carefully.
Given two strings X and Y of length n and m respectively, design a dynamic programming...
Given two strings X and Y of length n and m respectively, design a dynamic programming based algorithm to finnd a super-string Z of minimum length such that both X and Y are subsequence of Z. Note that characters in X and Y do not need to appear consecutively in Z as long as they appear in the same order in Z as in X or Y . Design an other algorithm for solving the same problem but with three...
Solve the following problem by Dynamic Programming: Maximize z = (y1 + 2)^2 + y2 *...
Solve the following problem by Dynamic Programming: Maximize z = (y1 + 2)^2 + y2 * y3 + (y4 - 5)^2 subject to y1 + y2 + y3 + y4 <= 5 yi >= 0 and integer, i = 1, 2, 3, 4
Choose a problem that lends to an implementation that uses dynamic programming. Clearly state the problem...
Choose a problem that lends to an implementation that uses dynamic programming. Clearly state the problem and then provide high-level pseudocode for the algorithm. Explain why this algorithm can benefit from dynamic programming.
what is the time complexity of the edit distance ("ALASKA" vs "ALABAMA" example) dynamic programming algorithm?...
what is the time complexity of the edit distance ("ALASKA" vs "ALABAMA" example) dynamic programming algorithm? what is the space complexity of the edit distance ("ALASKA" vs "ALABAMA" example) dynamic programming algorithm?
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT