Data Structures and algorithms using dynamicProgramming

Presentation on DSA using dynamic programming

1. Dynamic Programming Marzieh Eskandari NJIT 1/125

2. Definition Dynamic Programming refers to simplifying a complicated problem by breaking it down into simpler sub-problems in a recursive manner . 2/125

3. Dynamic Programing: Steps Define a couple of restricted small subproblems and a “Table” for their solutions Find a Recursive Relation between the main solution and solutions of smaller problems use an inductive method for constructing the main solution by using the solutions of smaller problems 3/125

4. Example 1: Fibonacci’s series int fib( int n) { if(n==1 || n==2) return 1; return fib(n-1)+fib(n-2); } F(1)=F(2)=1, F(n)=F(n-1)+F(n-2) 4/125

5. Example 1: Fibonacci’s series fib(5) fib(4) fib(3) fib(3) fib(2) fib(2) fib(1) fib(2) fib(1) 5/125

6. Recursive Algorithm: Time Complexity   6/125

7. Fibonacci’s series: DP Approach fib( int n) { F[0]=F[1]=1; for( i =2;i<= n;i ++) F[ i ]=F[i-1]+F[i-2]; } 1 - - - - - 1 F 1 2 - - - - 1 F 1 2 3 - - - 1 F 1 2 3 5 - - 1 F fib(5)=? - - - - - - - F   7/125

8. Binomial Coefficients/ Pascal triangle 8/125   n=0 1 n=1 1 1 n=2 1 2 1 n=3 1 3 3 1 n=4 1 4 6 4 1 n=5 1 5 10 10 5 1

9. Example 2: Binomial Coefficients int BC( int n, int r) { if(r==0 || n==r) return 1; return BC(n-1,r)+BC(n-1,r-1 ); } n>=r: C( r,r )=C(n,0)=1, C( n,r )=C(n-1,r-1)+C(n-1,r) 9/125

10. Example 2: Binomial Coefficient C(4,2) C(3,2) C(3,1) C(2,2) C(2,1) C(2,1) C(2,0) C(1,1) C(1,0) C(1,1) C(1,0) 10/125

11. Recursive Algorithm: Time Complexity   11/125

12. Example 2: Binomial Coefficient 1 2 3 4 0 1 2 3 4 12/125  

13. Example 2: Binomial Coefficient 1 2 3 4 0 1 2 3 4 1 2 3 4 0 1 2 3 4 13/125  

14. Example 2: Binomial Coefficient int BC( int n, int r) { for( i =0;i<= n;i ++) for(j=0;j<= r;j ++) if( i >=j) { if(j==0 || i ==j) M[ i ][j]=1; else M[ i ][j]=M[i-1][j]+M[i-1][j-1]; } return M[n][r]; } 1 2 3 4 0 1 2 3 4 1 1 1 1 1 1 1 1 1 14/125  

15. Example 2: Binomial Coefficient int BC( int n, int r) { for( i =0;i<= n;i ++) for(j=0;j<= r;j ++) if( i >=j) { if(j==0 || i ==j) M[ i ][j]=1; else M[ i ][j]=M[i-1][j]+M[i-1][j-1]; } return M[n][r]; } 1 2 3 4 0 1 2 3 4 1 1 1 1 1 1 1 1 1 M[4][2]=? 15/125  

16. Example 2: Binomial Coefficient 1 2 3 4 0 1 2 3 4 1 1 1 1 1 1 1 1 1 M[2][1]=? 16/125

17. Example 2: Binomial Coefficient 1 2 3 4 0 1 2 3 4 1 1 1 1 2 1 1 1 1 1 M[2][1]=? 17/125

18. Example 2: Binomial Coefficient 1 2 3 4 0 1 2 3 4 1 1 1 1 2 1 1 1 1 1 M[3][1]=? 18/125

19. Example 2: Binomial Coefficient 1 2 3 4 0 1 2 3 4 1 1 1 1 2 1 1 3 1 1 1 M[3][1]=? 19/125

20. Example 2: Binomial Coefficient 1 2 3 4 0 1 2 3 4 1 1 1 1 2 1 1 3 1 1 1 M[3][2]=? 20/125

21. Example 2: Binomial Coefficient 1 2 3 4 0 1 2 3 4 1 1 1 1 2 1 1 3 3 1 1 1 M[3][2]=? 21/125

22. Example 2: Binomial Coefficient 1 2 3 4 0 1 2 3 4 1 1 1 1 2 1 1 3 3 1 1 1 M[4][1]=? 22/125

23. Example 2: Binomial Coefficient 1 2 3 4 0 1 2 3 4 1 1 1 1 2 1 1 3 3 1 1 4 1 M[4][1]=? 23/125

24. Example 2: Binomial Coefficient 1 2 3 4 0 1 2 3 4 1 1 1 1 2 1 1 3 3 1 1 4 1 M[4][2]=? 24/125

25. Example 2: Binomial Coefficient 1 2 3 4 0 1 2 3 4 1 1 1 1 2 1 1 3 3 1 1 4 6 1 M[4][2]=? 25/125

26. Binomial Coefficient: Time Complexity int BC( int n, int r) { for( i =0;i<= n;i ++) for(j=0;j<= r;j ++) if( i >=j) { if(j==0 || i ==j) M[ i ][j]=1; else M[ i ][j]=M[i-1][j]+M[i-1][j-1]; } return M[n][r]; } 26/125  

27. Example 3: Floyd’s Method Given a weighted directed graph, find the shortest path between every pair of nodes. A D C E G B 1 1 5 9 3 2 4 2 3 3 A to B A to C A to D A to E B to A B to C B to D B to E C to A C to B C to D C to E D to A D to B D to C D to E E to A E to B E to C E to D 27/125

28. Example 3: Floyd’s Method A D C E G B 1 1 5 9 3 2 4 2 3 3 A-B A-D-C A-D A-D-E B-D-E-A B-C B-D B-D-E C-D-E-A C-D-E-A-B C-D C-D-E D-E-A D-E-A-B D-C D-E E-A E-A-B E-A-D-C E-A-D 28/125 Given a weighted directed graph, find the shortest path between every pair of nodes.

29. Example 3: Floyd’s Method A D C E G B 1 1 5 9 3 2 4 2 3 3 Lengths of all 20 shortest paths 29/125 Given a weighted directed graph, find the shortest path between every pair of nodes.

30. Example 3: Floyd’s Method A D C E G B 1 1 5 9 3 2 4 2 3 3 A to B: 1 A to C: 3 A to D: 1 A to E: 4 B to A: 8 B to C: 3 B to D:2 B to E: 5 C to A: 10 C to B: 11 C to D: 4 C to E: 7 D to A: 6 D to B: 7 D to C: 2 D to E: 3 E to A: 3 E to B: 4 E to C: 6 E to D: 4 30/125 Given a weighted directed graph, find the shortest path between every pair of nodes.

31. Graph: Representation A D C E G B 1 1 5 9 3 2 4 2 3 3 A B C D E A 1 8 1 5 B 9 3 2 8 C 8 8 4 8 D 8 8 2 3 E 3 8 8 8 W 31/125 W[ i ][j]=weight of edge from vertex i to j

32. Shortest paths: Representation A D C E G B 1 1 5 9 3 2 4 2 3 3 A B C D E A 1 3 1 4 B 8 3 2 5 C 10 11 4 7 D 6 7 2 3 E 3 4 6 4 D 32/125 D[ i ][j]=length of shortest path from vertex i to j

33. Optimal Substructure A B C SP(A,B)=P1+P2 If P1 is not the shortest path between A and B, let P3 is the shortest path between A and C. So we have: | P3|+|P2|<|P1|+|P2|=|SP(A,B)| That is a contradiction. P1 P2 P3 33/125

34. Defining subproblems Find the shortest path between all vertices when the graph is restricted to the first k vertices ({v 1 ,v 2 ,v 3 ,…, v k }) and start and target vertices . v1 v4 v3 v5 v2 1 1 5 9 3 2 4 2 3 3 k=3 34/125

35. Defining subproblems Find the shortest path between all vertices when the graph is restricted to the first k vertices ({v 1 ,v 2 ,v 3 ,…, v k }) and start and target vertices. v1 v3 v2 1 9 3 k=3 35/125

36. Subproblems : Example v1 v3 v2 1 3 K=3 9 d(v1,v2)=1 d(v1,v3)=4 36/125 d( vi,vj ): length of shortest path from vi to vj

37. v4 2 4 2 Subproblems : Example v1 v3 v2 1 3 K=3 9 d(v1,v2)=1 d(v1,v3)=4 d(v1, v4 )=1 1 37/125

38. v5 5 3 Subproblems : Example v1 v3 v2 1 3 K=3 9 d(v1,v2)=1 d(v1,v3)=4 d(v1,v4)=1 d(v1, v5 )=5 38/125

39. Subproblems : Example v1 v3 v2 1 3 K=3 9 d(v1,v2)=1 d(v1,v3)=4 d(v1,v4)=1 d(v1,v5)=5 d(v2,v1)=9 d(v2,v3)=3 39/125

40. v4 2 4 2 d(v1,v4)=1 1 Subproblems : Example v1 v3 v2 1 3 K=3 9 d(v1,v2)=1 d(v1,v3)=4 d(v2, v4 )=2 d(v1,v5)=5 d(v2,v1)=9 d(v2,v3)=3 40/125

41. d(v1,v4)=1 Subproblems : Example v1 v3 v2 1 3 K=3 9 d(v1,v2)=1 d(v1,v3)=4 d(v2,v4)=2 d(v1,v5)=5 d(v2,v1)=9 d(v2,v3)=3 v5 5 3 d(v2, v5 )=14 41/125

42. d(v1,v4)=1 Subproblems : Example v1 v3 v2 1 3 K=3 9 d(v1,v2)=1 d(v1,v3)=4 d(v2,v4)=2 d(v1,v5)=5 d(v2,v1)=9 d(v2,v3)=3 d(v2,v5)=14 d(v3,v1)=∞ d(v3,v2)=∞ 42/125

43. v4 2 4 2 1 d(v1,v4)=1 Subproblems : Example v1 v3 v2 1 3 K=3 9 d(v1,v2)=1 d(v1,v3)=4 d(v2,v4)=2 d(v1,v5)=5 d(v2,v1)=9 d(v2,v3)=3 d(v2,v5)=14 d(v3,v1)=∞ d(v3,v2)=∞ d(v3, v4 )=4 43/125

44. v5 5 3 d(v1,v4)=1 Subproblems : Example v1 v3 v2 1 3 K=3 9 d(v1,v2)=1 d(v1,v3)=4 d(v2,v4)=2 d(v1,v5)=5 d(v2,v1)=9 d(v2,v3)=3 d(v2,v5)=14 d(v3,v1)=∞ d(v3,v2)=∞ d(v3,v4)=4 d(v3, v5 )=∞ 44/125

45. d(v1,v4)=1 Subproblems : Example v1 v3 v2 1 3 k= 3 9 d(v1,v2)=1 d(v1,v3)=4 d(v2,v4)=2 d(v1,v5)=5 d(v2,v1)=9 d(v2,v3)=3 d(v2,v5)=14 d(v3,v1)=∞ d(v3,v2)=∞ d(v3,v4)=4 d(v3,v5)=∞ d(v4,v1)=∞ d(v4,v2)=∞ d(v4,v3)=2 d(v4,v5)=3 d(v5,v1)=3 d(v5,v2)=4 d(v5,v3)=7 d(v5,v4)=4 45/125

46. Subproblems : Representation v1 v4 v3 v5 v2 1 1 5 9 3 2 4 2 3 3 v1 v2 v3 v4 v5 v1 1 4 1 5 v2 9 3 2 14 v3 ∞ ∞ 4 ∞ v4 ∞ ∞ 2 3 v5 3 4 7 4 D (3) D [ i ][j]=length of shortest path between vi and vj in the graph restricted to vertices {v1,v2,…, vk } (k) 46/125

47. Notations D =W (0) D =D (n) D (k) D (k+1) D =W (0) D (1) D (2) D (3) … D =D (n) 47/125

48. Calculating Ds vi vj D [ i ][j] (k+1) 48/125

49. Calculating Ds vi vj D [ i ][j] (k+1) vi vj vi vj Vk+1 49/125

50. Calculating Ds vi vj D [ i ][j] (k+1) vi vj vi vj Vk+1 D (k) [ i ][j] D [ i ][k+1]+D [k+1][j] (k) (k) D [ i ][k+1]+D [k+1][j], (k) (k) D [ i ][j]=min{ (k+1) D [ i ][j]} (k) 50/125

51. Shortest Path: Example v1 v4 v3 G v2 5 15 50 15 5 15 5 v1 v2 v3 v4 v1 5 ∞ ∞ v2 50 15 5 v3 30 ∞ 15 v4 15 ∞ 5 W 30 51/125

52. Shortest Path: Example v1 v2 v3 v4 v1 5 ∞ ∞ v2 50 15 5 v3 30 35 15 v4 15 20 5 D D =W (0) (1) v1 v2 v3 v4 v1 5 ∞ ∞ v2 50 15 5 v3 30 ∞ 15 v4 15 ∞ 5 52/125

53. Shortest Path: Example v1 v2 v3 v4 v1 5 20 10 v2 45 15 5 v3 30 35 15 v4 15 20 5 D D (2) (3) v1 v2 v3 v4 v1 5 20 10 v2 50 15 5 v3 30 35 15 v4 15 20 5 53/125

54. Shortest Path: Example D =D (4) v1 v2 v3 v4 v1 5 15 10 v2 20 10 5 v3 30 35 15 v4 15 20 5 54/125

55. Floyd’s Method: Algorithm Floyd( int W[][], int n) { D=W; //initializing D for(k=1;k<= n;k ++) //calculating D k for( i =1;i<= n;i ++) for(j=1;j<= n;j ++) D[ i ][j]=min{D[ i ][j],D[ i ][k]+D[k][j]}; return D; }   55/125

56. Floyd’s Method: Algorithm Floyd( int W[][], int n) { D=W; //initializing D for(k=1;k<= n;k ++) //calculating D k for( i =1;i<= n;i ++) for(j=1;j<= n;j ++) if(D[ i ][k]+D[k][j]<D[ i ][j]) D[ i ][j]=D[ i ][k]+D[k][j]; return D; }   56/125

57. Shortest Paths! Rows and columns of P: v 1 to v n P[ i ][j]=r: shortest path from v i to v j passes through v r P[ i ][j]=0: edge v i v j is the shortest path from v i to v j How can I calculate P? How can I use P for finding shortest paths? 57/125

58. Shortest Paths! P[ i ][j]=r: shortest path from v i to v j passes through v r P[ i ][j]=0: edge v i v j is the shortest path from v i to v j v1 v2 v3 v4 v1 4 2 v2 4 4 v3 1 v4 1 P 58/125

59. Shortest Paths! v1 v2 v3 v4 v1 4 2 v2 4 4 v3 1 v4 1 P SP(v1,v3)=?? v1 v3 59/125 P[ i ][j]=r: shortest path from v i to v j passes through v r P[ i ][j]=0: edge v i v j is the shortest path from v i to v j

60. Shortest Paths! v1 v2 v3 v4 v1 4 2 v2 4 4 v3 1 v4 1 P SP(v1,v3)=?? P[v1][v3]=4 v1 v3 v4 60/125 P[ i ][j]=r: shortest path from v i to v j passes through v r P[ i ][j]=0: edge v i v j is the shortest path from v i to v j

61. Shortest Paths! v1 v2 v3 v4 v1 4 2 v2 4 4 v3 1 v4 1 P SP(v1,v3)=?? P[v1][v3]=4 1. SP(v1,v4)=? 2. SP(v4,v3)=? v1 v3 v4 61/125 P[ i ][j]=r: shortest path from v i to v j passes through v r P[ i ][j]=0: edge v i v j is the shortest path from v i to v j

62. Shortest Paths! v1 v2 v3 v4 v1 4 2 v2 4 4 v3 1 v4 1 P SP(v1,v3)=?? P[v1][v3]=4 1. P[v1][v4]=? 2. P[v4][v3]=? v1 v3 v4 62/125 P[ i ][j]=r: shortest path from v i to v j passes through v r P[ i ][j]=0: edge v i v j is the shortest path from v i to v j

63. Shortest Paths! v1 v2 v3 v4 v1 4 2 v2 4 4 v3 1 v4 1 P SP(v1,v3)=?? P[v1][v3]=4 1. P[v1][v4]=2 2. P[v4][v3]=0 v1 v3 v4 63/125 P[ i ][j]=r: shortest path from v i to v j passes through v r P[ i ][j]=0: edge v i v j is the shortest path from v i to v j

64. Shortest Paths! v1 v2 v3 v4 v1 4 2 v2 4 4 v3 1 v4 1 P SP(v1,v3)=?? P[v1][v3]=4 1. P[v1][v4]=2 2. P[v4][v3]=0 v1 v2 64/125 v4 v3 P[ i ][j]=r: shortest path from v i to v j passes through v r P[ i ][j]=0: edge v i v j is the shortest path from v i to v j

65. Shortest Paths! v1 v2 v3 v4 v1 4 2 v2 4 4 v3 1 v4 1 P SP(v1,v3)=?? P[v1][v3]=4 1. P[v1][v4]=2 1.1. P[v1][v2]=0 1.2. P[v2][v4]=0 2. P[v4][v3]=0 v1 v2 65/125 v3 v4 P[ i ][j]=r: shortest path from v i to v j passes through v r P[ i ][j]=0: edge v i v j is the shortest path from v i to v j

66. Shortest Paths! v1 v2 v3 v4 v1 4 2 v2 4 4 v3 1 v4 1 P SP(v1,v3)=?? P[v1][v3]=4 1. P[v1][v4]=2 1.1. P[v1][v2]=0 1.2. P[v2][v4]=0 2. P[v4][v3]=0 v2 66/125 v3 v4 v1 P[ i ][j]=r: shortest path from v i to v j passes through v r P[ i ][j]=0: edge v i v j is the shortest path from v i to v j

67. Calculating P vi vj D [ i ][j] (k+1) vi vj vi vj Vk+1 P[ i ][j]=k+1 D [ i ][k+1]+D [k+1][j] : P[ i ][j]=k+1 (k) (k) If D [ i ][j]= (k+1) 67/125

68. Floyd’s Algorithm Floyd(int W[][], int n) { D=W; P=0; for(k=1;k<= n;k ++) for( i =1;i<= n;i ++) for(j=1;j<= n;j ++) if(D[ i ][k]+D[k][j]<D[ i ][j]) { D[ i ][j]=D[ i ][k]+D[k][j]; P[ i ][j]=k+1; } return D; } 68/125

69. Example 4: Matrix Chain Multiplication Given a sequence of matrices, find the most efficient way to multiply these matrices together. Decide in which order to perform the multiplications to minimize the number of all regular multiplications. A: 13x5 B: 5x89 AxB = (13x89)x5 multiplications = 89 13 69/125 x i j i j

70. Example 4: Matrix Chain Multiplication Given a sequence of matrices, find the most efficient way to multiply these matrices together. Decide in which order to perform the multiplications to minimize the number of all scaler multiplications. A: 13x5 B: 5x89 C:89x3 D: 3x34 ( ( ( AB ) C ) D ) : ( 13x5x89 )+( 13x89x3 )+( 13x3x34 )=10582 ( ( AB ) ( CD ) ) : ( 13x5x89 )+( 3x89x34 )+( 13x89x34 )=54201 ( ( A ( BC ) ) D ) : ( 5x89x3 )+( 13x5x3 )+( 13x3x34 )=2856 ( A ( ( BC ) D ) ) : ( 5x89x3 )+( 5x34x3 )+( 13x5x34 )=4055 ( A ( B ( CD ) ) ) : ( 89x3x34 )+( 5x89x34 )+( 13x5x34 )=26418 70/125

71. MCM: Brute Force Approach The number of all orders in which we parenthesize the product of n matrices is the Catalan number:   71/125

72. MCM: Notations A = d i d i-1 i A =A A A … A A 1 2 3 n-1 n A : x i d i-1 d i A : x d d n A : x 1 d d 1 A : x 2 d 1 d 2 A : x 3 d 2 d 3 A : x n-1 d n-2 d n-1 A : x n d n-1 d n … A A i i+1 Number of multiplications of is d d i+1 d i-1 i 72/125

73. Orders! / Minimum number of multiplications! ( ( ( ( A 1 A 2 )( A 3 A 4 ) ) A 5 ) A 6 )( ( ( A 7 A 8 ) A 9 )( A 10 ( A 11 A 12 ) ) ) 73/125 A 1 A 2 A 3 A 4 A 5 A 6 A 7 A 8 A 9 A 10 A 11 A 12

74. Defining subproblems Find the most efficient way to multiply the following matrices together: For i >=j, M[ i ][j]=0 M[1][n]=Optimum number of multiplications. A x A x … x A i i+1 j M[ i ][j]=Minimum number of multiplications in product Ai Ai+1 … Aj , i <j 74/125

75. Calculating M[i][j] A A … A i i+1 j d d j d i-1 i M[i+1][j]+ d d j d i-1 i+1 M[ i ][i+1]+M[i+2][j]+ d d j d i-1 i+2 M[ i ][i+2]+M[i+3][j]+ d d j d i-1 k M[ i ][k]+M[k+1][j]+ … … d d j d i-1 j-3 M[ i ][j-3]+M[j-2][j]+ d d j d i-1 j-2 M[ i ][j-2]+M[j-1][j]+ d d j d i-1 j-1 M[ i ][j-1]+ (A … A )(A … A ) i i+2 i+3 j (A … A )(A … A ) i j-3 j-2 j (A A )(A … A ) i i+1 i+2 j A (A … A ) i i+1 j … (A … A )(A … A ) i k k+1 j … (A … A )(A A ) i j-2 j-1 j (A … A ) A i j-1 j MIN 75/125

76. Calculating M[ i ][j] A A … A i i+1 j (A … A )(A … A ) i k k+1 j d d j d i-1 k M[ i ][j]= MIN { M[ i ][k]+M[k+1][j] + } i <=k<j MIN M[ i ][ i ]= 0 76/125

77. Calculating M 1 2 3 4 : n 1 2 3 4 … n M[ i ][j]=? A A … A i i+1 j 77/125

78. Calculating M M[ i ][j]=? A A … A i i+1 j i <=j 1 2 3 4 : n 1 2 3 4 … n 78/125

79. Calculating M Diagonal 0 Diagonal 1 Diagonal 2 Diagonal n-2 Diagonal n-1 M[ i ][ i ]: n M[ i ][i+1]: n-1 M[ i ][i+2]: n-2 M[ i ][ i+d ]: n-d M[ i ][i+n-2]: 2 M[1][1+n-1]: 1 Diagonal d: M[ i ][ i+d ], 1<= i <=n-d M[ i ][j] lies on Diagonal j- i 1 2 3 4 : n 1 2 3 4 … n Diagonal d 79/125

80. Calculating M M[ i ][ i ]=0 1 2 3 4 : n 1 2 3 4 … n 80/125

81. Calculating M d d i+1 d i-1 k M[ i ][i+1]= MIN { M[ i ][k]+M[k+1][i+1]+ }= i <=k<i+1 d d i+1 d i-1 i M[ i ][ i ]+M[i+1][i+1]+ i+1 =d d d i-1 i d d 2 d 1 1 2 3 4 : n 1 2 3 4 … n 81/125

82. Calculating M d d i+2 d i-1 k M[ i ][i+2]= MIN { M[ i ][k]+M[k+1][i+2]+ }= i <=k<i+2 d d i+2 d i-1 i MIN{M[ i ][ i ]+M[i+1][i+2]+ d d i+2 d i-1 i+1 , M[ i ][i+1]+M[i+2][i+2]+ } 1 2 3 4 : n 1 2 3 4 … n 82/125

83. Calculating M d d j d i-1 k M[ i ][j]= MIN { M[ i ][k]+M[k+1][j] + } i <=k<j k- i < j- i j-k-1< j- i 1 2 3 4 : n 1 2 3 4 … n 83/125 Diagonal j- i

84. Matrix Chain Multiplication int MCM(int n, int d[]) { for( i =1;i<= n;i ++) M[ i ][ i ]=0; // Diagonal 0 for(d=1;d<=n-1;d++) // Diagonals 1 to n-1 for( i =1;i<= n-d;i ++) { j= i+d ; M[ i ][j]=Min(M[ i ][k]+M[k+1][j]+d[i-1]*d[k]*d[j]); } return M[1][n]; } i <=k<=j-1   84/125

85. Orders! P[ i ][j]=k: the optimal order is (A … A )(A … A ) i k k+1 j 85/125

86. Orders! P[ i ][j]=k: the optimal order is P[ i ][i+1]= i (A … A )(A … A ) i k k+1 j 86/125

87. Orders! P A 1 A 2 A 3 A 4 A 5 A 6 P[ i ][j]=k: the optimal order is P[ i ][i+1]= i (A … A )(A … A ) i k k+1 j 1 2 3 4 5 6 1 2 3 4 5 6 1 1 1 1 3 4 5 4 5 5 87/125

88. Orders! P A 1 A 2 A 3 A 4 A 5 A 6 P[1][6]=1 P[ i ][j]=k: the optimal order is (A … A )(A … A ) i k k+1 j 1 2 3 4 5 6 1 2 3 4 5 6 1 1 1 1 3 4 5 4 5 5 A 1 (A 2 A 3 A 4 A 5 A 6 ) 88/125

89. Orders! P A 1 A 2 A 3 A 4 A 5 A 6 P[1][6]=1 P[2][6]=5 P[ i ][j]=k: the optimal order is P[ i ][i+1]= i (A … A )(A … A ) i k k+1 j 1 2 3 4 5 6 1 2 3 4 5 6 1 1 1 1 3 4 5 4 5 5 A 1 (A 2 A 3 A 4 A 5 A 6 ) A 1 ((A 2 A 3 A 4 A 5 ) A 6 ) 89/125

90. Orders! P A 1 A 2 A 3 A 4 A 5 A 6 P[1][6]=1 P[2][6]=5 P[2][5]=4 P[ i ][j]=k: the optimal order is P[ i ][i+1]= i (A … A )(A … A ) i k k+1 j 1 2 3 4 5 6 1 2 3 4 5 6 1 1 1 1 3 4 5 4 5 5 A 1 (A 2 A 3 A 4 A 5 A 6 ) A 1 ((A 2 A 3 A 4 A 5 ) A 6 ) A 1 (((A 2 A 3 A 4 )A 5 ) A 6 ) 90/125

91. Orders! P A 1 A 2 A 3 A 4 A 5 A 6 P[1][6]=1 P[2][6]=5 P[2][5]=4 P[2][4]=3 P[ i ][j]=k: the optimal order is j>=i+1 (A … A )(A … A ) i k k+1 j 1 2 3 4 5 6 1 2 3 4 5 6 1 1 1 3 3 4 5 4 5 5 A 1 (A 2 A 3 A 4 A 5 A 6 ) A 1 ((A 2 A 3 A 4 A 5 ) A 6 ) A 1 (((A 2 A 3 A 4 )A 5 ) A 6 ) A 1 ((((A 2 A 3 )A 4 )A 5 ) A 6 ) 91/125

92. Orders! ( ( ( ( A 1 A 2 )( A 3 A 4 ) ) A 5 ) A 6 )( ( ( A 7 A 8 ) A 9 )( A 10 ( A 11 A 12 ) ) ) 1. P[1][12]=6 1.1. P[1][6]=5 1.1.1. P[1][5]=4 1.1.1.1. P[1][4]=2 1.2. P[7][12]=9 1.2.1. P[7][9]=8 1.2.2. P[10][12]=10 92/125

93. Matrix Chain Multiplication int MCM(int n, int d[]) { for( i =1;i<= n;i ++) M[ i ][ i ]=0; // Diagonal 0 for(d=1;d<=n-1;d++) // Diagonals 1 to n-1 for( i =1;i<= n-d;i ++) { j= i+d ; M[ i ][j]=Min(M[ i ][k]+M[k+1][j]+d[i-1]*d[k]*d[j]); P[ i ][j]= min_k ; } return M[1][n]; } 1<=k<=j-1   93/125

94. 65 40 Example 5: Optimal Binary Search Tree 50 60 60 50 55 70 65 75 75 40 70 40 Depth=2 Depth=3 Balanced 94/125

95. Binary Tree Search node BTS( int x, node root) { p=root; while (p!=NULL) { if( p.key ==x) return p; if( p.key <x ) p= p.left ; else p= p.right ; } return NULL; }   95/125 40 50 60 55 70 65 75 Search time for x= depth(x)+1

96. Optimal Binary Search Tree Given a sorted array key of search keys and an array P[0.. n-1], where P[i] is the number of searches for . Construct a binary search tree of all keys such that the total cost of all the searches is as small as possible.   Key Frequencies k 1 p 1 k 2 p 2 … … k n-1 p n-1 k n p n 96/125

97. Example Key Frequencies k 1 12 k 2 10 k 3 8 k 4 20 97/125 k 1 k 2 k 4 k 3

98. Example Key Frequencies k 1 12 k 2 10 k 3 8 k 4 20 98/125   k 1 k 2 k 4 k 3 2 1 2 3

99. Optimal Binary Search Tree Search time for Minimizing search time   Key Frequencies k 1 p 1 k 2 p 2 … … k n-1 p n-1 k n p n 99/125

100. Normalization Key Frequencies k 1 12 k 2 10 k 3 8 k 4 20 100/125   k 1 k 2 k 4 k 3 2 1 2 3        

101. Example Key Frequencies k 1 .24 k 2 .2 k 3 .16 k 4 .4 101/125   k 1 k 2 k 4 k 3 2 1 2 3

102. Optimal Binary Search Tree Minimizing average search time p i =1/n: AVL   Key Frequencies k 1 p 1 k 2 p 2 … … k n-1 p n-1 k n p n   102/125

103. Optimal Binary Search Tree 60 50 40 60 40 50 K P 40 0.7 50 0.2 60 0.1 3(0.7)+2(0.2)+1(0.1)=2.6 40 60 50 2(0.7)+1(0.2)+2(0.1)=1.8 40 50 60 1(0.7)+2(0.2)+3(0.1)=1.4 40 50 60 1(0.7)+3(0.2)+2(0.1)=1.5 2(0.7)+3(0.2)+1(0.1)=2.1 103/125

104. Optimal Binary Search Tree k r k i ,k 2 … ,k r-1 k r+1 ,k r+2 … , k j L R A[ i ][j]=Minimum Average Search Time for a binary tree of keys: k i , k i+1 , …,k j-1 , k j : 1<= i <= j <=n 104/125

105. Optimal Binary Search Tree k i A[ i ][ i ]=p i 105/125

106. Optimal Binary Search Tree k r k 1 ,k 2 … ,k r-1 k r+1 ,k r+2 … , k n L A[1][n]=? R 106/125

107. Optimal Substructure k i , … ,k r-1 k r+1 , … , k j L R k r T*   107/125

108. Optimal Binary Search Tree k r k 1 ,k 2 … ,k r-1 k r+1 ,k r+2 … , k n L T R     108/125

109. Optimal Substructure k i , … ,k r-1 k r+1 , … , k j L R   k r T 109/125

110. Calculating A[ i ][j] k r k i k j k i+1 k i k j-1 k j … …               110/125

111. Representing A 1 2 3 : n n+1 0 1 2 … n-1 n     111/125

112. Representing A 1 2 3 : n n+1 0 1 2 … n-1 n       112/125

113. Representing A 1 2 3 : n n+1 0 1 2 … n-1 n       113/125  

114. Representing A 1 2 3 : n n+1 0 1 2 … n-1 n Diagonal 0 Diagonal 1 Diagonal d Diagonal n-2 Diagonal n-1 Diagonal -1 A[ i ][i-1]: n+1 A[ i ][ i ]: n A[ i ][i+1]: n-1 A[ i ][ i+d ]: n-d A[ i ][i+n-2]: 2 A[1][1+n-1]: 1 Diagonal d: A[ i ][ i+d ], 1<= i <=n-d A[ i ][j] lies on Diagonal j- i 114/125

115. Representing A           115/125

116. Representing A 1 2 3 : n n+1 0 1 2 … n-1 n 116/125

117. Representing A 1 2 3 : n n+1 0 1 2 … n-1 n p 1 p 2 … … p n 117/125

118. Optimal Binary Search Tree int OBST(int n, int P[]) { for( i =1;i<=n+1;i++) A[ i ][i-1]=0; // Diagonal -1 for( i =1;i<= n;i ++) A[ i ][ i ]=P[ i ]; // Diagonal 0 for(d=1;d<=n-1;d++) // Diagonals 1 to n-1 for( i =1;i<= n-d;i ++) { j= i+d ; A[ i ][j]=Min(A[ i ][r-1]+A[r+1][j]+P[ i ]+…+P[j]); } return A[1][n]; } 1<=r<=j   118/125

119. Constructing Optimal Tree R[ i ][j]=r: k r is the root in the optimal Tree of k i … k j R[ i ][i-1]=0, R[ i ][ i ]= i 119/125

120. Constructing Optimal Tree R[ i ][j]=r: k r is the root in the optimal Tree of k i … k j R[ i ][ i ]= i P 1 2 3 4 5 6 0 1 2 3 4 5 1 1 1 1 4 2 3 4 5 3 4 5 4 5 5 120/125

121. Constructing Optimal Tree R[ i ][j]=r: k r is the root in the optimal Tree of k i … k j R[ i ][i-1]=0, R[ i ][ i ]= i P 1 2 3 4 5 6 0 1 2 3 4 5 1 1 1 1 4 2 3 4 5 3 4 5 4 5 5 R[1][5]=4 k 4 k 1 … k 3 k 5 121/125

122. Constructing Optimal Tree R[ i ][j]=r: k r is the root in the optimal Tree of k i … k j R[ i ][i-1]=0, R[ i ][ i ]= i P 1 2 3 4 5 6 0 1 2 3 4 5 1 1 1 1 4 2 3 4 5 3 4 5 4 5 5 R[1][3]=1 k 4 k 2 , k 3 k 5 k 1 122/125

123. Constructing Optimal Tree R[ i ][j]=r: k r is the root in the optimal Tree of k i … k j R[ i ][i-1]=0, R[ i ][ i ]= i P 1 2 3 4 5 6 0 1 2 3 4 5 1 1 1 1 4 2 3 4 5 3 4 5 4 5 5 R[2][3]=3 k 4 k 5 k 1 k 3 k 2 123/125

124. Optimal Binary Search Tree int OBST(int n, int P[]) { for( i =1;i<=n+1;i++) {A[ i ][i-1]=0;R[ i ][i-1]=0;} // Diagonal -1 for( i =1;i<= n;i ++) {A[ i ][ i ]=P[ i ];R[ i ][ i ]= i ;} // Diagonal 0 for(d=1;d<=n-1;d++) // Diagonals 1 to n-1 for( i =1;i<= n-d;i ++) { j= i+d ; A[ i ][j]=Min(A[ i ][r-1]+A[r+1][j]+P[ i ]+…+P[j]); R[ i ][j]= min_r ; } return A[1][n]; } 1<=r<=j   124/125

125. Any Question?? Have a nice day! 125/125