Matrix chain multiplication

Question 1

If I do A(nxm) * B(m*k)
what is the dimensions of C

Answer 1

n x k

Question 2

How many ways to parenthesise a chain of n matrices

Answer 2

sum to n-1 i starts at 1
p(i)p(n-i)

p(1) = 1

Question 3

what is the run time of Matrix chain multiplication (with memoization)

Answer 3

O(n^3)

Question 4

what is the run time of Matrix chain multiplication (without memoization)

Answer 4

O(2^n)

thats how many ways there are to parentesize

Question 5

what is the recursive formula for matrix chain multiplication

Answer 5

m[i,j] -> min(m[i,k]+m[k,j]+ pi−1​pk​pj)

where i,k is the left sub chain
and k,j is the right sub chain
and pi-1pkpj is the cost to multiply the two

when p is in this form
p=[3,7,6,2,9]
chain of 3x7 * 7x6 .. etc