unit3_Dynamic_Progrghaiajawzjabagamming1.pptx

unit3_Dynamic_Progrghaiajawzjabagamming1.pptx

1. CSC 3504: Design and Analysis of Algorithms-I Mrs. Sujata Sathe Assistant Professor Computer Science Department Fergusson College (Autonomous), Pune Mrs Sujata Sathe

2. Mrs Sujata Sathe   Unit-III Dynamic Programming Strategy used in DP, difference between DP and DandC Principle of optimality (Tabulation and Memoization ) Matrix chain multiplication Problem   Example 1:Matrix Chain multiplication Example 2:Matrix Chain multiplication Shortest paths theory Floyd Warshall Algorithm Examples of calculating shortest path using Floyd Warshall Algorithm Analysis of Floyd Warshall Algorithm Bellman - ford algorithm Examples of calculating shortest path using Bellman - ford Algorithm Concept of String editing and its usage Example 1: String Editing Example 2: String Editing Knapsack problem strategy 0/1 Knapsack problem Examples of knapsack Longest common Subsequence Example 1: LCS Example 2: LCS Travelling Salesman Problem Example 1: TSP Example 2: TSP Example 3: TSP Optimal Binary Search Trees Example 1: OBST Example 2: OBST Content

3. Mrs Sujata Sathe Finding all pairs shortest path 1->2 1->3 2->1 2->3 3->1 3->2

4. Mrs Sujata Sathe 1 2 3 8 7 5 2 9 1 1 2 3 1 1 8 2 9 5 3 2 7 A Q.Find the shortest path using floyd-warshall algorithm A 1 Now intermediate vertex is 1 i.e so keep the First row and first column as it is and calculate other A[ i,j ] values using formula 1 2 3 1 1 8 2 9 5 3 2 A 1 [2,3]= min {A [2,3], A [2,1]+A [1,3] } =min{5,9+8}=5 5 A 1 [3,2]= min {A [3,2], A [3,1]+A [1,2] } =min{7,2+1}= 3 3

5. Mrs Sujata Sathe A 1 1 2 3 1 1 8 2 9 5 3 2 3 Now intermediate vertex is 2 so keep the 2 nd row and 2 nd column as it is and calculate other A[ i,j ] values using formula A 2 1 2 3 1 1 6 2 9 5 3 2 3 A 2 [1,3]= min {A 1 [1,3], A 1 [1,2]+A 1 [2,3] } i =1,j=3 k=2 =min{8,1+5}= 6 6 A 2 [3,1]= min {A 1 [3,1], A 1 [3,2]+A 1 [2,1] } i =3,j=1, k=2 =min{2,3+9}=2 2 Now intermediate vertex is 3 so keep the 3 rd row and 3 rd column as it is and calculate other A[ i,j ] values using formula A 3 1 2 3 1 6 2 5 3 2 3 A 3 [1,2]= min {A 2 [1,2], A 2 [1,3]+A 2 [3,2] } i = 1,j=2 ,k=3 =min{1,6+3}=1 1 A 3 [2,1]= min {A 2 [2,1], A 2 [2,3]+A 2 [3,1] } i =2,j=1, k=3 =min{9, 5+2}= 7 7

6. Mrs Sujata Sathe

7. Mrs Sujata Sathe 1 2 3 4 1 4 ∞ 3 2 ∞ 2 1 3 5 3 ∞ 4 1 ∞ 2 Q. Use the floyd-warshall algorithm and find all pairs shortest paths for the following adjacency weighted matrix Cost Matrix =A A 1 Now intermediate vertex is 1 i.e so keep the First row and first column as it is and calculate other A[ i,j ] values using formula 1 2 3 4 1 4 ∞ 3 2 ∞ 2 1 3 5 3 8 4 1 5 2 A 1 [2,3]= min {A [2,3], A [2,1]+A [1,3] } i=2, j=3 , k= 1 =min{2, ∞ + ∞ }=2 A 1 [2,4]= min {A [2,4], A [2,1]+A [1,4] } i=2, j=4 , k= 1 =min{1, ∞ + 3}= 1 A 1 [3,2]= min {A [3,2], A [3,1]+A [1,2] } i=3, j=2 , k= 1 =min{3,5 + 4}=3 A 1 [3,4]= min {A [3,4], A [3,1]+A [1,4] } i=3, j=4, k= 1 =min{∞,5 + 3}=8 A 1 [4,2]= min {A [4,2], A [4,1]+A [1,2] } i=4, j=2, k= 1 =min{∞,1 + 4}=5 A 1 [4,3]= min {A [4,3], A [4,1]+A [1,3] } i=4, j=3, k= 1 =min{2,1 + ∞}=2

8. Mrs Sujata Sathe A 1 1 2 3 4 1 4 ∞ 3 2 ∞ 2 1 3 5 3 8 4 1 5 2 Now intermediate vertex is 2 so keep the 2 nd row and 2 nd column as it is and calculate other A[ i,j ] values using formula A 2 1 2 3 4 1 4 6 3 2 ∞ 2 1 3 5 3 4 4 1 5 2 A 3 1 2 3 4 1 4 6 3 2 7 2 1 3 5 3 4 4 1 5 2 Now intermediate vertex is 3 so keep the 3 rd row and 3 rd column as it is and calculate other A[ i,j ] values using formula

9. Mrs Sujata Sathe A 3 1 2 3 4 1 4 6 3 2 7 2 1 3 5 3 4 4 1 5 2 Now intermediate vertex is 4 so keep the 4th row and 4 th column as it is and calculate other A[ i,j ] values using formula A 4 1 2 3 4 1 4 5 3 2 2 2 1 3 5 3 4 4 1 5 2

10. Mrs Sujata Sathe v4 v3 v1 v2 3 1 6 1 Use bellman –ford algorithm to find shortest path from v1 Source vertex = V1 D[vi]=∞ and D[v1]= 0 2 3 1 Edges list (1,2) (1,3) (2,3) (2,4) (3,4) Consider the edge (1,2) d[2]=∞ d[1]+cost[1,2]=0+1=1 so update d[2] = 1 Consider the edge ( 1,3) d[3]=∞ d[1]+ cost[1,3]=0+3=3, so update d[3] = 3 Relaxtion:if there is an edge from u,v If d[v]> d[u] +cost[ u,v ] Then update d[v]= d[u] +cost[ u,v ] Otherwise don’t change D[v1] D[v2] D[v3] D[v4] ∞ ∞ ∞ 1 1 2 3 2 1 2 3 3 Do the relaxation of edges till n-1 times where n is the no of vertices D[v1] D[v2] 1 D[v3] 2 D[v4] 3

11. Mrs Sujata Sathe 1 6 4 5 2 3 7 6 -1 5 5 -2 -2 -1 1 3 3 Edge list (1,2),(1,3),(1,4),(2,5),(3,2),(3,5),(4,3),(4,6),(5,7),(6,7) 1 3 3 4 5 Relaxtion:if there is an edge from u,v If d[v]> d[u] +cost[ u,v ] Then update d[v]= d[u] +cost[ u,v ] Otherwise don’t change

12. Mrs Sujata Sathe Edge list (1,2),(1,3),(1,4),(2,5),(3,2),(3,5),(4,3),(4,6),(5,7),(6,7) Iteration D[v1] D[v2] D[v3] D[v4] D[v5] D[v6] D[v7] ∞ ∞ ∞ ∞ ∞ ∞ 1 3 3 5 5 4 7 2 1 3 5 2 4 5 3 1 3 5 4 3 4 1 3 5 4 3 D[v1] D[v2] 1 D[v3] 3 D[v4] 5 D[v5] D[v6] 4 D[v7] 3 Solution Set

13. Mrs Sujata Sathe Longest Common Subsequence Str 1 : a c d p s t r i u x t m n Str 2 :g m n u x p i c s n Sequence : m n n u x n p i n S1 = {B, C, D, A, A, C, D} S2 = {A, C , D, B, A, C } Seq: {A,A,C }, {C, D,A,C }, {B,A,C},{D,A,C},{B,C}, {A.C}..... LCS={C,D,A,C}

14. Mrs Sujata Sathe b d \o 1 2 a b c d \o 1 2 3 4 A B int LCS( i,j ) { if (A[i] = = ‘\0’ | | B[j] = = ‘\0 ’) return 0; elseif ( A[i] = = B[j]) 1+ LCS(i+1, j+1); else max(LCS(i+1,j),LCS(i,j+1)); } A[0], B[0] b ,a A[1], B[0] d ,a A[0], B[1] b ,b A[2], B[0] \0 , a A[1], B[1] d , b A[2], B[1] \0 ,b A[1], B[2] d ,c A[2], B[2] \0 ,c A[1], B[3] d ,d A[2], B[4] \0 ,\0 1+ 1+0=1 1 1 1 1 A[1], B[2] d ,c 1+ A[1], B[2] d ,c A[2], B[2] \0 ,c A[1], B[3] d ,d A[2], B[4] \0 ,\0 1+ 1+0=1 1 1 1 2 2 2 2 2 1 1 1 1 a b c d \0 0 1 2 3 4 b 0 d 1 \0 2

15. Mrs Sujata Sathe S1: { b,d }, S2 :{ a,b,c,d } 1 1 1 1 1 2 0 1 2 3 4 1 2 a b c d b d If s1[i] == s2[j] ( if there is a match) then 1+ diagonal element If not Then max( Prev row, prev col) d b LCS = { b,d }

16. Mrs Sujata Sathe S1: { c,b,d,a }, S2:{ a,c,a,d,b } 1 1 1 1 1 1 1 2 1 1 2 2 1 1 2 2 2 0 1 2 3 4 5 a c a d b 1 2 3 4 c b d a b c Lcs : c,b

17. Mrs Sujata Sathe String Editing Transform X= abcdg to Y= aecbf and cost of inserting and deleting is 1 and that of replacing is 2 Delete all char from X, insert the char from Y,Tot Oper = 5 + 5 =10 Replace b with e, replace d with b, replace g with f= Tot operation =6

18. Mrs Sujata Sathe Transform X= aabab to Y= babb and cost of inserting and deleting is 1 and that of replacing is 2 Delete all char from X, insert the char from Y, Tot Oper = 5 + 4 =9 Delete first two chars from X, Then insert the char b at the end , Tot operation =2+1=3

19. Mrs Sujata Sathe

20. Mrs Sujata Sathe

21. Mrs Sujata Sathe

22. Mrs Sujata Sathe Q.Transform X= adceg to Y= abcfg Rows=tot chars from x+1 Cols=tot chars from y+1 1 2 3 4 5 1 1 2 3 4 2 1 1 2 3 4 3 2 2 1 2 3 4 3 3 2 2 3 5 4 4 3 3 2 null a b c f g null a d c e g Insert deletion Replace a d c e g a b c f g If r ≠ c If r = c just copy the diagonal element REPLACE REMOVE INSERT MIN(DIAG, UP,LEFT)+1 REPLACE REMOVE INSERT Copy diagonal ele

23. Mrs Sujata Sathe Q. Find the edit ( Levenshtein ) distance between the two strings A= sitting, and B= kitten. 1 2 3 4 5 6 1 1 2 3 4 5 6 2 2 1 2 3 4 5 3 3 2 1 2 3 4 4 4 3 2 1 2 3 5 5 4 3 2 2 3 6 6 5 4 3 3 2 7 7 6 5 4 4 3 null k i t t e n null s i t t i n g s i t t i n g k i t t e n We did 2 replacements and 1 deletion

24. Mrs Sujata Sathe Travelling Salesman Problem Given a graph G=(V,E) which is directed weightED graph, Let us assume that verter1 is the starting node. The problem involves computation of the minimum cost path that starting from vertex 1 visits all other vertices exactly once and returns back to the starting vertex. g( i,S ) = min { Cik + g( k,S -{k}) k€S g(1,{2,3,4}) = min { C12 + g(2, {3,4}), C13 + g(3,{2,4}), C14 + g(4, {2,3})} k€{2,3,4} Base case: g( v,ɸ )= Cv1 1 3 4 2

25. Mrs Sujata Sathe 10 15 20 5 9 10 6 13 12 8 8 9 1 2 3 4 1 2 3 4 So the starting vertex is 1. g( i,S ) = min { Cik + g( k,S -{k}) k€S g(1 ,{2,3,4}) = min { C12 + g(2, {3,4}), C13 + g(3,{2,4}), C14 + g(4, {2,3})} k €{2,3,4} 1 3 2 4 C12 + g(2, {3,4 }) 10+ g(2,{3,4}) C13 + g(3,{2,4 }) 15 + g(3,{2,4 }) C14 + g(4, {2,3 }) 20 + g(4, {2,3 }) 3 4 C23 + g(3, { 4 }) 9 + g(3,{4}) 9+20=29 C24 + g(4, {3}) 10 + g(4,{3})= 10+15=25 4 C34 + g(4, ɸ) 12 + 8 =20 3 C43 + g(3, ɸ) 9 + 6 =15 START NODE 2 4 C32 + g(2, {4}) 13 + g(2,{4})= 13+18=31 C34 + g(4, {2}) 12 + g(4,{2})= 12+13=25 4 C24 + g(4, ɸ) 10+ 8 = 18 2 C42 + g(2, ɸ) 8 + 5 = 13 2 3 C42 + g(2, {3}) 8 + g(2, {3})= 8+15=23 C43 + g(3, {2}) 9 + g(3, {2})= 9+18=27 3 C23 + g(3, ɸ) 9 + 6= 15 2 C32 + g(2, ɸ) 13 + 5= 18 g(1,{2,3,4}) = min { C12 + g(2, {3,4}), C13 + g(3,{2,4}), C14 + g(4, {2,3 })} = min{ 10+25, 15+25, 20+23} =min{35, 40, 43} =35

26. Mrs Sujata Sathe

27. Mrs Sujata Sathe 10 15 20 5 9 10 6 13 12 8 8 9 10 15 20 5 9 10 6 13 12 8 8 9 1 2 3 4 1 2 3 4

28. Mrs Sujata Sathe 0/1 Knapsack Problem W is the capacity of of the Bag, wi and pi is the weight and profit associated with each each item xi. The total profit earned is Σ xi*pi Solution set is X={x1,x2….. xn } Q given below is the weight and profit of the items and capacity of the bag is 15. Solve the problem to maximize the profit Solution set {0/1,0/1,0/1} x1 x2 x3 weights 10 5 7 profits 90 110 80

29. Mrs Sujata Sathe W=8, P={1,2,5,6} W={2,3,4,5} 1 1 1 1 1 1 1 1 2 2 3 3 3 3 1 2 5 5 6 7 7 1 2 5 6 6 7 8 0 1 2 3 4 5 6 7 8 1 2 3 4 V Pi Wi 1 2 2 3 5 4 6 5 Weights I T E M S V[ i,w ] = max{ V[i-1,w], V[i-1,w-w[i]]+ P[i]} V[4,1]=max { V[3. 1], V[3, 1-5] + 6 } = max{ 0, V[3,-4]+6 } = 0 Solution set = {0,1,0,1} 8 items X1 X2 X3 X4 1 1 8-6=2 2-2=0

30. Mrs Sujata Sathe Q2. Capacity=3, Profit={1,6,4} Weight={1,2,4} Q3. Capacity=12, Profit={14,20,24, 30} Weight={2,4,6,10}

31. Mrs Sujata Sathe Matrix Chain Multiplication A X B ≠ BX A…not commutative A X B m*n x*y Rule for matrix multiplication is that the col of First matrix should be equal to the row of the second matrix. (n= x) The dimensions of the resultant matrix = m*y Given three matrices A, B, and C, you can perform matrix multiplication as A.(B.C), (A.B). C A X B m*n x*y Given a set of matrices {A1,A2,…An} with the dimensions {p0*p1,p1*p2,….,pn-1* pn }, find the optimal order of matrices such that the cost of multiplication is optimal. A:5X4, B:4X3 = Resultant Matrix (AXB): 5X3 = R A:5X4 B:4X3 R: 5X3 The multiplication cost of the resultant matrix = 5*4*3=60

32. Mrs Sujata Sathe Q. Consider the following three matrices A:2X3 ; B: 3X4; C: 4X3 What are the possible orderings? What is the optimal order? (A XB)X C= (2*3*4)+(2*4*3)=24+24=48 AX(BXC)= (3*4*3)+(?) (A1.A2).(A3.A4) A1.(A2.A3).A4 .. .

33. Mrs Sujata Sathe A1.A2.A3.A4 5x4 4 x 6 6 X 2 2 x 7 120 88 48 104 84 1 2 3 4 1 2 3 4 M 1 1 2 3 3 1 2 3 4 1 2 3 4 S M[1,1]=0, M[2,2]=0, M[3,3]=0,M[4,4] M[1,2]=120 (A1.A2) 5X4 4X6 Cost= 5*4*6=120 M[2,3]=48 A2.A3 4X6 6X2 Cost= 4*6*2=48 M[3,4]=84 A3.A4 6X2 2X7 Cost= 6*2*7=84 M[1,3] = 88 ie A1.A2.A3 A1.(A2.A3) (A1.A2).A3 5X4 4X6 6X2 5X4 4X6 6X2 M[1,1]+M[2,3]+5*4*2 M[1,2]+M[3,3]+ 5*6*2 =0+48+40 =120+0+60 =88 =180 M[2,4]= i.e A2.A3.A4 A2.(A3.A4) ( A2.A3).A4 4X6 6X2 2X7 4X6 6X2 2X7 M[2,2]+M[3,4]+4*6*7 M[2,3]+M[4,4]+ 4*2*7 =0+84+168 =48+0+56 =252 = 104

34. Mrs Sujata Sathe 120 88 158 48 104 84 1 2 3 4 1 2 3 4 M 1 1 3 2 3 3 1 2 3 4 1 2 3 4 S M[1,4]= min{M[1,1]+ M[2,4]+5*4*7, M[1,2]+M[3,4]+5*6*7,M[1,3]+M[4,4] +5*2*7} = {0+104+140, 120+84+210, 88+0+70} =158

35. Mrs Sujata Sathe A1.A2.A3.A4 4x5 5 x 3 3 X 2 2 x 7 60 70 126 30 100 42 1 2 3 4 1 2 3 4 M 1 1 3 2 3 3 1 2 3 4 1 2 3 4 S M[1,1]=0, M[2,2]=0, M[3,3]=0,M[4,4]=0, M[1,2]=60 (A1.A2) 4X5 5X3 Cost= 4*5*3=60 M[2,3]=30 ( A2.A3) M[2,2]+M[3,3]+5X3X2 M[3,4]= ( A3.A4)

36. Mrs Sujata Sathe A1.A2.A3.A4.A5 4x5 5 x 3 3 X 2 2 x 7 7X2 1 2 3 4 5 1 2 3 4 5 M 1 2 3 4 5 1 2 3 4 5 S

37. Mrs Sujata Sathe Optimal Binary Search Tree A BST is a binary tree that possesses the following properties Each node of a BST has one key, All the nodes on the LHS of a BST is less than or equal to the keys stored in the root. All the nodes on the RHS of a BST are greater than or equal to the keys stored in the root

38. Mrs Sujata Sathe Optimal Binary Search Tree Keys = 10,20,30,40,50,60,70 40 60 20 10 30 50 70 Keys = 10,20,30 Frequency=3,2,5 10 20 30 30 10 20 10 30 20 30 1 10 30 20 20 To find the node 50, how many comparisons are done 3 comparisons To find element 29 4comp 3*1 2*2 5*3 1+2+3/3= 6/3=2 1 2 3 1+2+3/3= 6/3=2 1 2 2 1+2+2/3= 5/3=<2 1+2+3/3= 6/3=2 1+2+3/3= 6/3=2 3+4+15= 22 3*1+5*2+2*3= 19 2*1+3*2+5*2= 17 5*1+3*2+2*3= 17 5*1+2*2+3*3= 18

39. Mrs Sujata Sathe C[ i,j ] =min {C[i,k-1]+ C[ k,j ]}+ w[ i,j ] i< k≤j 1 2 3 4 10 20 30 40 4 2 6 3 keys frequency No 4 8 1 20 3 26 3 2 10 3 16 3 6 12 3 3 1 2 3 4 1 2 3 4 i j C C[0,0]= C[1,1]=C[2,2]=C[3,3]=C[4,4]=0 C[0,1]=4 Consider only 1 key i.e10 & Freq =4 C[1,2]=2 C[2,3]=6 C[3,4]=3 C[0,2] means there are 2 keys 10, 20 For j-i=1 1-0=1, C[0,1] 2-1=1, C[1,2] 3-2=1,C[2,3] 4-3=1,C[3,4] For j-i=2 2-0=2, C[0,2] 3-1=2, C[1,3] 4-2=2, C[2,4] 4 w[0,4]= Σ F(i) i=1 10 20 20 10 4*1 2*2 2*1 4*2 4*1+2*2= 8 2*1+4*2= 10 C[1,3] means there are 2 keys 20 , 30 C[1,3]= min C[1,1]+ C[2,3], k=2,3 C[1,2]+C[3,3], + w[1,3] =min{0+6+8, 2+0+8} =min{14,10} w[1,3]=2+6=8 Cost of OBST=26 and the root node is 3 3 r [0,4]=3 1 4 r[0,2] r[3,4] 2 r[0,0] r[1,2] r[1,1] r[2,2] r[3,3] r[4,4] 30 10 20 40