Answer:
b.
Matrix chain multiplication
M[i,j] = M[i,k] + M[(k+1),j] + p[i-1]*p[k]*p[j] i<=k<j
p[] = {5,10,3,12,5,50}
M[0][0] = 0,M[1][1] = 0,M[2][2] = 0,M[3][3] = 0,M[4][4] = 0,M[5][5] = 0,
M[1][2] = M[1][1]+M[2][2]+p[0]*p[1]*p[2] = 0+0+5*10*3 = 150
M[2][3] = M[3][3]+M[2][2]+p[1]*p[2]*p[3] = 0+0+10*3*12 = 360
M[3][4] = M[3][3]+M[4][4]+p[2]*p[3]*p[4] = 0+0+3*12*5 = 180
M[4][5] = M[4][4]+M[5][5]+p[3]*p[4]*p[5] = 0+0+12*5*50 = 3000
M[1][3] = min{M[1][1]+M[2][3]+p[0]*p[1]*p[3] , M[1][2]+M[3][3]+p[0]*p[2]*p[3]}
= {0 + 360 + 600 , 150+0+180} = {960,330} = 330
M[2][4] = min{M[2][2]+M[3][4]+p[1]*p[2]*p[4] , M[2][3]+M[4][4]+p[1]*p[3]*p[4]}
= {0 + 180 + 150 , 360+0+600} = {960,330} = 330
M[3][5] = min{M[3][3]+M[4][5]+p[2]*p[3]*p[5] , M[3][4]+M[5][5]+p[2]*p[4]*p[5]}
= {0 + 3000 + 1800 , 180+0+750} = {4800,930} = 930
M[1][4] = min{M[1][1] + M[2][4] +p[0]*p[1]*p[4] ,M[1][2] + M[3][4] +p[0]*p[2]*p[4] ,
M[1][3] + M[4][4] +p[0]*p[3]*p[4]}
{0+330+250 , 150+180+75 , 330+0+300} = 405
M[2][5] = min{M[2][2] + M[3][5] +p[1]*p[2]*p[5] ,M[2][3] + M[4][5] +p[1]*p[3]*p[5] ,
M[2][4] + M[5][5] +p[1]*p[4]*p[5]}
{0+930+1500 , 360+3000+6000,330+0+2500} = 2430
M[1][5] = min{M[1][1] +M[2][5]+p[0]*p[1]*p[5] , M[1][2] +M[3][5]+p[0]*p[2]*p[5],
M[1][3] +M[4][5]+p[0]*p[3]*p[5] , M[1][4] +M[5][5]+p[0]*p[4]*p[5]}
{0+2430+2500 , 150+930+750 , 330+3000+3000 , 405+0+1250} = 1655
(a)
MemoizedCutRod(p, n)
r: array(0..n) := (0 => 0, others =>MinInt)
return MemoizedCutRodAux(p, n, r)
MemoizedCutRodAux(p, n, r)
if r(n) = 0 and then n /= 0 then -- check if need to calculate a new solution
q: int := MinInt
for i in 1 .. n loop
q := max(q, p(i) + MemoizedCutRodAux(p, n-i, r))
end loop
end if
r(n) := q
end if
return r(n)
