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.
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?
Using the dynamic programming-based algorithm for chain matrix multiplcation, show the best way to multiply a...
Using the dynamic programming-based algorithm for chain matrix multiplcation, show the best way to multiply a chain of matrices with dimensions that are: 10x5, 5x2, 2x20, 20x12, 12x4 and 4x60. Finally, use the resulting tables to provide the complete optimal parenthesization of the matrix chain product A0 · A1 · A2 · A3 · A4 · A5.
Implement the dynamic algorithm of 0-1 knapsack problem in Java. The following table shows 10 items,...
Implement the dynamic algorithm of 0-1 knapsack problem in Java. The following table shows 10 items, their values and weights. The maximum weight capacity of the knapsack is 113. What could be the maximum value of the knapsack and the most valuable set of items that fit in the knapsack? Item Weight Value 1 32 727 2 40 763 3 44 60 4 20 606 5 1 45 6 29 370 7 3 414 8 13 880 9 6 133...
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT