Algorithmic Toolbox | Week 5

Course Name: Algorithmic Toolbox

These are Algorithmic Toolbox Week 5 Programming Assignment Coursera Answers

Programming Assignment 5: Dynamic Programming 1

5-1: Money Change Again

import math

money = int(input())
denominations = [1, 3, 4]
minCoins = [0] + [math.inf]*money

for i in range(1, money+1):
    for j in denominations:
        if i>=j:
            coins = minCoins[i-j]+1
            if coins < minCoins[i]:
                minCoins[i] = coins

print(minCoins[money])

5-2: Primitive Calculator

import math

n = int(input())

num_operations = [0, 0] + [math.inf]*(n-1)

for i in range(2, n+1):
    temp1, temp2, temp3 = [math.inf]*3

    temp1 = num_operations[i-1] + 1 
    if i%2 == 0: temp2 = num_operations[i//2] + 1
    if i%3 == 0: temp3 = num_operations[i//3] + 1
    min_ops = min(temp1, temp2, temp3)
    num_operations[i] = min_ops

print(num_operations[n])

nums = [n]
while n!=1:
    if n%3 ==0 and num_operations[n]-1 == num_operations[n//3]:
        nums += [n//3]
        n = n//3
    elif n%2 ==0 and num_operations[n]-1 == num_operations[n//2]:
        nums += [n//2]
        n = n//2
    else:
        nums += [n-1]
        n = n - 1

print(' '.join([str(i) for i in nums][::-1]))

These are Algorithmic Toolbox Week 5 Programming Assignment Coursera Answers

5-3: Edit Distance

def edit_distance(first_string, second_string):
    m, n = len(first_string), len(second_string)
    
    # Create a (m+1)x(n+1) matrix to store the edit distances
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    
    # Initialize the base cases
    for i in range(m + 1):
        dp[i][0] = i
    for j in range(n + 1):
        dp[0][j] = j
    
    # Fill the dp table
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if first_string[i - 1] == second_string[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]
            else:
                dp[i][j] = min(dp[i - 1][j] + 1,    # Deletion
                               dp[i][j - 1] + 1,    # Insertion
                               dp[i - 1][j - 1] + 1)  # Substitution
    
    return dp[m][n]

if __name__ == "__main__":
    import sys
    input = sys.stdin.read
    data = input().split()
    first_string = data[0]
    second_string = data[1]
    print(edit_distance(first_string, second_string))

These are Algorithmic Toolbox Week 5 Programming Assignment Coursera Answers

5-4: Longest Common Subsequence of Two Sequence

def lcs2(first_sequence, second_sequence):
    n = len(first_sequence)
    m = len(second_sequence)
    
    dp = [[0] * (m + 1) for _ in range(n + 1)]
    
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if first_sequence[i - 1] == second_sequence[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    
    return dp[n][m]

if __name__ == '__main__':
    n = int(input())
    a = list(map(int, input().split()))
    assert len(a) == n

    m = int(input())
    b = list(map(int, input().split()))
    assert len(b) == m

    print(lcs2(a, b))

These are Algorithmic Toolbox Week 5 Programming Assignment Coursera Answers

See also Algorithmic Toolbox | Week 6

5-5: Longest Common Subsequence of Three Sequence

def lcs3(first_sequence, second_sequence, third_sequence):
    n = len(first_sequence)
    m = len(second_sequence)
    l = len(third_sequence)
    
    dp = [[[0] * (l + 1) for _ in range(m + 1)] for __ in range(n + 1)]
    
    # Fill the dp table
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            for k in range(1, l + 1):
                if first_sequence[i - 1] == second_sequence[j - 1] and first_sequence[i - 1] == third_sequence[k - 1]:
                    dp[i][j][k] = dp[i - 1][j - 1][k - 1] + 1
                else:
                    dp[i][j][k] = max(dp[i - 1][j][k], dp[i][j - 1][k], dp[i][j][k - 1])
    
    return dp[n][m][l]

if __name__ == '__main__':
    n = int(input())
    a = list(map(int, input().split()))
    assert len(a) == n

    m = int(input())
    b = list(map(int, input().split()))
    assert len(b) == m

    q = int(input())
    c = list(map(int, input().split()))
    assert len(c) == q

    print(lcs3(a, b, c))

These are Algorithmic Toolbox Week 5 Programming Assignment Coursera Answers

More Weeks of the course: Click Here

More Coursera courses: https://progiez.com/coursera

These are Algorithmic Toolbox Week 5 Programming Assignment Coursera Answers

Programming Assignment 5: Dynamic Programming 1

Similar: