Question

MODIFIED-BOTTOM-UP-CUT-ROD(p, n, c) to return not only the value but the actual solution, too. Hint: It is similar to how array s is maintained in EXTENDED-BOTTOM-UP-CUT-ROD. Now you need to initialize not just array r but also array s in EXTENDED-MEMOIZED-1 let r[0..n] and s[0..n] be new arrays2 r[0] = 03 for j = 1 to n4 q = p[ j ]5 s[ j ] = j6 for i = 1 to j - 17 if q < p[ i ]+ r[ j - i ] - c8 q = p[ i ]+ r[ j - i ] - c9 s[ j ] = i10 r[ j ] = q11 return r and s3

Answer 1

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)