Algorithm Analysis

Assignment #5

Wasim Chami
03/06/2025
64210085
Contents
Question 1 : Dynamic Programming...................................................................................3
The algorithm for an optimal parenthesization of a matrix chain product as discussed
inthe class.......................................................................................................................3
Code:...............................................................................................................................3
result...............................................................................................................................4
Part (b): Time Complexity................................................................................................4
Part (c): Loop Invariant for Matrix Chain Multiplication....................................................5
Question 2 greedy algorithm..............................................................................................6
represent V as the sum of products using minimum possiblenumber of integers from L .
........................................................................................................................................6
Implementation in python :.............................................................................................6
Result :............................................................................................................................7
B) Time Complexity.........................................................................................................7
C) Loop Invariant of the Greedy Algorithm......................................................................8
Question 1 : Dynamic Programming
The algorithm for an optimal parenthesization of a matrix chain
product as discussed inthe class.
Code:
import sys
# function to perform matrix chain multiplication using dynamic programming
def matrix_chain_order(p):
n = len(p) - 1 # number of matrices is one less than number of dimensions

# m[i][j] will hold the minimum number of multiplications needed to compute Ai..Aj
m = [[0 for _ in range(n)] for _ in range(n)]

# s[i][j] will hold the index k at which we split the product for optimal cost
s = [[0 for _ in range(n)] for _ in range(n)]

# l is the chain length

for l in range(2, n + 1):
for i in range(0, n - l + 1):
j=i+l-1
m[i][j] = sys.maxsize # set to infinity initially
for k in range(i, j):
# calculate cost = cost of multiplying A[i..k] + A[k+1..j] + cost of final multiplication
q = m[i][k] + m[k + 1][j] + p[i] * p[k + 1] * p[j + 1]
if q < m[i][j]:
m[i][j] = q
s[i][j] = k # store the optimal split point
return m, s

# recursive function to print optimal parenthesis structure

def print_optimal_parens(s, i, j):
if i == j:
print(f"A{i + 1}", end="") # use A1..An
else:
print("(", end="")
print_optimal_parens(s, i, s[i][j])
print_optimal_parens(s, s[i][j] + 1, j)
print(")", end="")

# function to run a test case and print the result

def run_test_case(dimensions, case_number):
print(f"\n🔹 test case {case_number}: dimensions = {dimensions}")
m, s = matrix_chain_order(dimensions)
print("optimal parenthesization:", end=" ")
print_optimal_parens(s, 0, len(dimensions) - 2)
print("\nminimum number of multiplications:", m[0][-1])

# extract x, y, z from the leftmost 6 digits of id: 996787

id_digits = "996787"
X = int(id_digits[0:2]) # 99
Y = int(id_digits[2:4]) # 67
Z = int(id_digits[4:6]) # 87

# test cases
dims1 = [5, 10, 3, X, 12, 5, 50, Y, 6]
dims2 = [5, 10, 50, 6, X, 15, 40, 18, Y, 30, 15, Z, 3, 12, 5]
dims3 = [50, 6, X, 15, 40, 18, Y, 5, 10, 3, 12, 5, Z, 40, 10, 30, 5]
# run the test cases
run_test_case(dims1, 1)
run_test_case(dims2, 2)
run_test_case(dims3, 3)
result

🔹 test case 1: dimensions = [5, 10, 3, 99, 12, 5, 50, 67, 6]

optimal parenthesization: ((A1A2)(((((A3A4)A5)A6)A7)A8))
minimum number of multiplications: 15990

🔹 test case 2: dimensions = [5, 10, 50, 6, 99, 15, 40, 18, 67, 30, 15, 87, 3, 12, 5]
optimal parenthesization: ((A1(A2(A3(A4(A5(A6(A7(A8(A9(A10(A11A12)))))))))))(A13A14))
minimum number of multiplications: 27915

🔹 test case 3: dimensions = [50, 6, 99, 15, 40, 18, 67, 5, 10, 3, 12, 5, 87, 40, 10, 30, 5]
optimal parenthesization: (A1((A2(A3(A4(A5(A6(A7(A8A9)))))))((((((A10A11)A12)A13)A14)A15)A16)))
minimum number of multiplications: 31035

Part (b): Time Complexity

 The algorithm uses Dynamic Programming.

 Let n be the number of matrices → n = len(p) - 1
 The time complexity is O(n³) due to the three nested loops:
 Two loops to fill the table m[i][j]
 One loop to find the best split point k
 So the overall time complexity is: O(n³)
 Part (c): Loop Invariant for Matrix Chain Multiplication

We focus on the loop:

python
Copy code
for l in range(2, n + 1): # chain length
for i in range(0, n - l + 1):
j=i+l-1
...
Loop Invariant Statement:
at the start of each iteration of the outer loop (for chain length l), the algorithm has
correctly computed the minimum number of scalar multiplications for all matrix chains of
length less than l.

1. Initialization:
When l = 2, only chains of 2 matrices are evaluated.

We directly compute and store the cost for all pairs (Ai × Ai+1) — base case is correct.

2. Maintenance:
At each step l, we use already-computed values for smaller chains (from earlier l-1, l-2,
etc.) to calculate cost for larger chains.

This ensures that m[i][k] and m[k+1][j] are already computed before we compute m[i][j].

3. Termination:
When the loop finishes, the invariant guarantees that all chain lengths 2 ≤ l ≤ n have
been considered.

So the value m[0][n-1] contains the minimum multiplication cost for the full sequence.
Question 2 greedy algorithm
represent V as the sum of products using minimum
possiblenumber of integers from L .
Implementation in python :
# function to implement the greedy sum-of-products algorithm
def greedy_sum_of_products(V, L):
# initialize result array r with zeros
R = [0 for _ in range(len(L))]

# iterate over each value in L

for i in range(len(L)):
# use the current largest possible number from L as many times as it fits in V
R[i] = V // L[i]
V = V % L[i]

return R

# function to display the result in the required format

def print_result(L, R):
terms = []
total = 0
for l, r in zip(L, R):
if r > 0:
terms.append(f"{l} * {r}")
total += l * r
print("V =", " + ".join(terms))
print("total value =", total)

# test function for three cases

def test_cases():
print("🔹 test case 1 (should produce minimum combination):")
V1 = 187
L1 = [20, 15, 12, 7, 3, 1]
R1 = greedy_sum_of_products(V1, L1)
print("L =", L1)
print("R =", R1)
print_result(L1, R1)
print("\n")

print("🔹 test case 2 (should produce minimum combination):")

V2 = 238
L2 = [19, 16, 13, 9, 4, 1]
R2 = greedy_sum_of_products(V2, L2)
print("L =", L2)
print("R =", R2)
print_result(L2, R2)
print("\n")

print("🔹 test case 3 (does NOT produce minimum combination):")

V3 = 200
L3 = [17, 13, 12, 6, 4, 1] # greedy fails here
R3 = greedy_sum_of_products(V3, L3)
print("L =", L3)
print("R =", R3)
print_result(L3, R3)
print("note: this may not be the minimum number of items.\n")

test_cases()
Result :

🔹 test case 1 (should produce minimum combination):

L = [20, 15, 12, 7, 3, 1]
R = [9, 0, 0, 1, 0, 0]
V = 20 * 9 + 7 * 1
total value = 187

🔹 test case 2 (should produce minimum combination):

L = [19, 16, 13, 9, 4, 1]
R = [12, 0, 0, 1, 0, 1]
V = 19 * 12 + 9 * 1 + 1 * 1
total value = 238

🔹 test case 3 (does NOT produce minimum combination):

L = [17, 13, 12, 6, 4, 1]
R = [11, 1, 0, 0, 0, 0]
V = 17 * 11 + 13 * 1
total value = 200

B) Time Complexity
The algorithm iterates once over the m values in list L, performing division and modulo in
constant time per step.

Time Complexity: O(m)

Where m is the number of values in L

This is efficient and fast, but not always optimal in solution quality.
C) Loop Invariant of the Greedy Algorithm
We consider the loop:
python
Copy code
for i in range(len(L)):
R[i] = V // L[i]
V = V % L[i]
Loop Invariant Statement:
At the start of each iteration i, the remaining value of V is equal to the original value
minus the sum of all previously computed terms from R[j] × L[j] for j < i.

1. Initialization:
Before the first iteration, V is the full input value, and nothing has been subtracted yet.

The invariant holds trivially.

2. Maintenance:
In each step, we subtract R[i] × L[i] from V, reducing it.

This maintains the invariant: the remaining V is the original minus the total so far.

3. Termination:
At the end, V becomes zero.

The sum of R[i] × L[i] for all i equals the original input value, confirming correctness of
the decomposition (though not necessarily optimality).