MCM

(i). MCM -Recursive

Python Code


def matrix_chain_multiplication_recursive(dims, i, j):
    if i == j:
        return 0
    
    min_cost = float('inf')
    
    for k in range(i, j):
        cost = matrix_chain_multiplication_recursive(dims, i, k) \
               + matrix_chain_multiplication_recursive(dims, k + 1, j) \
               + dims[i - 1] * dims[k] * dims[j]
        
        min_cost = min(min_cost, cost)
    
    return min_cost

# Example usage
matrix_dimensions = [10, 20, 30, 40, 50]
n = len(matrix_dimensions) - 1  # Number of matrices
result = matrix_chain_multiplication_recursive(matrix_dimensions, 1, n)
print("Minimum Scalar Multiplications:", result)

(ii). MCM - Memoization(TOP DOWN)

Python Code


def matrix_chain_multiplication_top_down(dims, i, j, memo):
    if i == j:
        return 0
    
    if memo[i][j] != -1:
        return memo[i][j]
    
    min_cost = float('inf')
    
    for k in range(i, j):
        cost = matrix_chain_multiplication_top_down(dims, i, k, memo) \
               + matrix_chain_multiplication_top_down(dims, k + 1, j, memo) \
               + dims[i - 1] * dims[k] * dims[j]
        
        min_cost = min(min_cost, cost)
    
    memo[i][j] = min_cost
    return min_cost

def matrix_chain_multiplication(dims):
    n = len(dims) - 1
    memo = [[-1] * (n + 1) for _ in range(n + 1)]
    return matrix_chain_multiplication_top_down(dims, 1, n, memo)

# Example usage
matrix_dimensions = [10, 20, 30, 40, 50]
result = matrix_chain_multiplication(matrix_dimensions)
print("Minimum Scalar Multiplications:", result)

(iii). MCM - Tabulation(Bottom UP)

Python Code


def matrix_chain_multiplication_bottom_up(dims):
    n = len(dims) - 1
    dp = [[float('inf')] * n for _ in range(n)]
    
    # Chain length 1 matrices cost 0 to multiply
    for i in range(n):
        dp[i][i] = 0
    
    for chain_length in range(2, n + 1):
        for i in range(n - chain_length + 1):
            j = i + chain_length - 1
            for k in range(i, j):
                cost = dp[i][k] + dp[k + 1][j] + dims[i] * dims[k + 1] * dims[j + 1]
                dp[i][j] = min(dp[i][j], cost)
    
    return dp[0][n - 1]

# Example usage
matrix_dimensions = [10, 20, 30, 40, 50]
result = matrix_chain_multiplication_bottom_up(matrix_dimensions)
print("Minimum Scalar Multiplications:", result)