Answer to Question #148629 in Algorithms for Altaf khan

Question

1. Compute the minimum number of multiplications required for the matrix chain A 1 × 5, B 5 × 10,
C 10 × 15, D 15 × 20, E 20 × 5. Show the contents of the dynamic programming table along with the
calculations considered. Also give the recurrence?
2. Compute the Longest Common Subsequence for the strings X = [ABCDABCAB] and Y = [BCBCB].
Show the contents of the dynamic programming table. Also give the recurrence?

Answer 1

1.

m[A,B] = 1*5*10 = 50

m[B,C] = 5*10*15 = 750

m[C,D] = 10*15*20 = 3000

m[D,E] = 15*20*5 = 1500

m[A,C] = min(m[A,B]+1*10*15, m[B,C] + 1*5*15) = min(50+150, 750+75) = 200

m[B,D] = min(m[B,C]+5*15*20, m[C,D] + 5*10*20) = min(750 + 1500, 3000 + 1000) = 2250

m[C,E] = min(m[C,D]+10*20*5, m[D,E] + 10*15*5) = min(3000 + 1000, 1500 + 750) = 2250

m[A,D] = min(m[A,C]+1*15*20, m[B,D] + 1*5*20, m[A,B] + m[C,D] + 1*10*20) = min(200+300, 2250+100, 50 + 3000 + 200) = 500

m[B,E] = min(m[B,D]+5*20*5, m[C,E] + 5*10*5, m[B,C] + m[D,E] + 5*15*5) = min(750+500, 2250+250, 750+1500+375) = 1250

m[A,E] = min(m[A,D] + 1*20*5, m[A,C] + m[D,E] + 1*15*5, m[A,B] + m[C,E] + 1*10*5, m[B,E] + 1*5*5) = min(500+100, 200+1500 + 75, 50+2250+50, 1250 + 25) = 600

ABCDE = (((AB)*C)*D)*E

2.

LCS(X,Y) = LCS(([ABCDABCAB], [BCBCB])) =

LCS(([ABCDABCA], [BCBC])^[B]) =

LCS(([ABCDABC], [BCBC])^[B]) =

LCS(([ABCDA], [BC])^[BCB])=

LCS(([ABC], [BC]))^[BCB])=

LCS(([A], []))^[BCBCB]) =

[BCBCB]