Longest Common Subsequence & Matrix Chain Multiplication

in this slide i will show about Longest Common Subsequence method & It;s Algorithm.Also show Matrix Chain Multiplication & it's Algorithm.

1. Longest common subsequence & Matrices chain multiplication Course Title : Algorithm Design And Analysis

2. 2 LONGEST COMMON SUBSEQUENCE The longest common subsequence ( LCS) problem  is the problem of finding the longest subsequence common to all sequences in a set of sequences (often just two sequences).

3. abc a b c ab bc ac cab c a b ca ab cb LCS= ab 3

4. Condition Table Value Sign If i =j=0 No sign If ( i,j >0) && X i = Y j C[i-1,j-1] Else if ( i,j >0 && X i = Y j ) If [C(i-1,j)>=C(i,j-1)] Else [C(i-1,j)<=C(i,j-1)] C[i-1,j] C[I,j-1] LONGEST COMMON SUBSEQUENCE

5. Example: Find the length of the longest subsequence present in both of them……. Seq1: ABCDEFG , Seq2: CDBAEF F E D C Seq1 A B C D E F G Seq2 C 1 1 1 1 1 D 1 2 2 2 2 B 1 1 2 2 2 2 A 1 1 1 2 2 2 2 E 1 1 1 2 3 3 3 F 1 1 1 2 3 4 4

6. m:=length(X) n:=length(Y) Let B=[1……m,1…..n]& C=[0……m,0…….n] For i =1 to n C[i,0]:=0 For j=1 to n C[0,j]:=0 For i =1 to n for j=1 to n If X i = Y j C[ I,j ]:=C[i-1,j-1] B[ i,j ]=“ “ Else if C[i-1,j]>=C[i,j-1] Algorithm

7. C[ i,j ]:=C[i-1,j] B[ i,j ]:=“ “ Else C[ i,j ]:=C[i,j-1] 18.B[ i,j ]:=“ “ 19.Return Algorithm

8. Definition: if we are given a sequence/chain of n Matrices ( A 1 ,A 2 ………A i ) where i =1,2…..n & A i has dimension P i-1 *P i to be multiplied and we wish to compute the product or parenthesis In a way that the total number of scalar multiplication is minimized. This process is known as Matrix Chain Multiplication. Goal of MCM: parenthesizing a chain of matrices so that it can have a dramatic impact on the cast evaluating multiplication of matrices or the product. Where it is being used: Compiler design for cost optimization. Database or query optimization. Rules to remember : -Multiplication is associative not commulative . Matrix chain multiplication

9. A 1 A 2 (5*4) (4*6) Dimension: A 1 A 2 = 5*6 =30 Cost : A 1 A 2 = 5*4*6 = 120 How does cost can be calculated?

10. If the matrices are A 1 A 2 A 3 (5*4) (4*6) (6*2) (A 1 A 2 )A 3 A 1 ( A 2 A 3 ) (A 1 A 2 )A 3 A 1 A 2 = 5*4*6 C 1 = 120 (A 1 A 2 )A 3 = 5*6*2 C 2 = 60 Total Cost = C 1 + C 2 =120 + 60 = 180

11. Law : How many parenthesizing could be possible? 2n c n P(n-1) = n+1 Note : if the matrices are A 1 , A 2, A 3 , A 4 then we take n=3 2*3 c 3 P(3-1) = 3+1 = 5

12. A 1 A 2 A 3 A 4 (5*4) (4*6) (6*2) (2*7) P P 1 P 1 P 2 P 2 P 3 P 3 P 4 2*3 c 3 P(3-1) = 3+1 = 5 How many parenthesizing could be possible?

13. m( i,i )= 0 m( j,j )= 0 m( i,j )= min ( i <=k<j) {m( i,k ) + m(k+1,j) + p i-1 *p k * p j } m(1,2)= min (1<=k<2) {m(1,1) + m(1+1,2) + p *p 1 * p 2 } = min (1<=k<2) {0 + 0+ 5 *4 *6} = 120 (for k=1)

14. m(2,3)= min (2<=k<3) {m(2,2) + m(3,3) + p 1 *p 2 * p 3 } = min (1<=k<3) {0 + 0+ 4 *6 *2} = 48 (for k= 2) m(3,4)= min (3<=k<4) {m(3,3) + m(4,4) + p 2 *p 3 * p 4 } = min (1<=k<4) {0 + 0+ 6 *2 *7} = 84 (for k= 3)

15. m(1,3)= min (1<=k<3) {m(1,1) + m(2,3) + p *p 1 * p 3 } + {m(1,2) + m(3,3) + p *p 2 * p 3 } = min (1<=k<3) {0 + 48+ 5 *4 *2} + {120 + 0 + 5 *6 *2} = min (1<=k<3) {88,180} = 88 (for k= 1) m(2,4)= min (2<=k<4) {m(2,2) + m(3,4) + p 1 *p 2 * p 4 } + {m(2,3) + m(4,4) + p 1 *p 3 * p 4 } = min (1<=k<4) {0 + 84+ 4 *6 *7} + {48 + 0 + 4 *2 *7} = min (1<=k<4) {272,104} = 104 (for k= 3)

16. m(1,4)= min (1<=k<4) {m(1,1) + m(2,4) + p *p 1 * p 4 } + {m(1,2) + m(3,4) + p *p 2 * p 4 } + {m(1,3) + m(4,4) + p *p 3 * p 4 } = min (1<=k<4) {0 + 104+ 5 *4 *7} + {120 + 84 + 5 *6 *7} + {88 + 0 + 5 *2 *7} = min (1<=k<4) {244,414,158} = 158 (for k= 3) Short : m(1,2) = 120 m(1,3) = 88 m(1,4) = 158 m(2,3) = 48 m(2,4) = 104 m(3,4) = 84

17. M[1………….m,1………..n] s[1……..n-1,2…………n] 120 88 158 48 104 84 1 1 3 2 3 3 For cost value For the value of k J=1 2 3 4 J = 2 3 4 i =1 2 3 4 i =1 2 3

18. For cost value For the value of k

19. 158, k=3 m( i,j ) m[1,4] m( i,k ) , m(k+1,j) m(1,3) , m(4,4) 88, k=1 m( i,j ) m[1,3] m( i,k ) , m(k+1,j) m(1,1) , m(2,3) A 4 A 1 48, k=2 m( i,j ) m[2,3] m( i,k ) , m(k+1,j) m(2,2) , m(3,3) A 2 A 3 A 1 A 2 A 3 A 4

20. Tree Diagram ????

21. A 1 A 2 A 3 A 4 ((A 1 (A 2 A 3 ))A 4 ) A 1 A 2 A 3 A 4 A 1 A 2 A 3 A 2 A 3 Tree Diagram

22. Thank You