110/6/2008 CSE 5311 Fall 2007M Kumar1Dynamic programming techniquesTopics•Basics of DP•Longest Common subsequence•0-1 Knapsack problem •Matrix-chain Multiplication• All-pairs Shortest pathsFurther ReadingChapter 6Textbook10/6/2008 CSE 5311 Fall 2007M Kumar2Dynamic programming•Solves problems by combining the solutions to subproblems•DP is applicable when subproblems are not independentSubproblems share subsubproblemsIn such cases a simple Divide and Conquer strategy solves common subsubproblems.•In DP every subproblem is solved just once and the solution is saved in a table for future reference (avoids re-computation).•DP is typically applied to optimization problems•A given problem may have many solutions, DP chooses the optimal solution.210/6/2008 CSE 5311 Fall 2007M Kumar3Four stages of Dynamic Programming♦Characterize the structure of an optimal solution♦Recursively define the value of an optimal solution♦Compute the value of an optimal solution in a bottom-up fashion♦Construct an optimal solution from computed results10/6/2008 CSE 5311 Fall 2007M Kumar4Longest common subsequenceA subsequence is formed from a list by deleting zero or more elements (the remaining elements are in order)A common subsequence of two lists is a subsequence of both. The longest common subsequence (LCS) of two lists is the longest among the common subsequences of the two lists. Example:abcabba and cbabac are two sequencesbaba is a subsequence in bothabcabba and cbabac310/6/2008 CSE 5311 Fall 2007M Kumar5abcabbababacbabac10/6/2008 CSE 5311 Fall 2007M Kumar6To find the length of an LCS of lists x and y, we need to find the lengths of the LCSs of all pairs of prefixes.a prefix is an initial sublist of a listIf x = (a1,a2,a3, . . ., am) and y = (b1,b2,b3, . . ., bn)0 ≤i ≤m and 0≤j≤nConsider an LCS of the prefix (a1,a2,a3, . . ., ai) from x and of the prefix (b1,b2,b3, . . ., bj) from y. If i or j = 0 then one of the prefixes is εand the only possible common subsequence between x and y is εand the length of the LCS is zero.410/6/2008 CSE 5311 Fall 2007M Kumar7L(i,j) is the length of the LCS of (a1,a2,a3, . . ., ai) and(b1,b2,b3, . . ., bj).e.g., a1a2a3a4a5a6a7(i=7) b1b2b3b4b5b6(j=6) suppose a2=b1; a4=b2; a5=b4; a7=b6. L(7,6) = 4 BASIS: If i+j = 0, then both i and j are zero and so the LCS is ε.INDUCTION: Consider i and j, and suppose we have already computed L(g,h) for any g and h such thatg+h < i+j.1.If either i or j is 0 then L(i,j) = 0.2.If i>0 and j>0, and ai≠ bjthen L(i,j) = max(L(i,j-1),L(i-1,j)).3.If i >0 and j> 0, and ai= bjthen L(i,j) = L(i-1,j-1)+1.10/6/2008 CSE 5311 Fall 2007M Kumar8ε a b c aε a c a b 0 0 0 0 00 1 1111.If either i or j is 0 then L(i,j) = 0.2.If i>0 and j>0, and ai≠ bjthen L(i,j) = max(L(i,j-1),L(i-1,j)).3.If i >0 and j> 0, and ai= bjthen L(i,j) = L(i-1,j-1)+1.0 1 1 2 20 1 1 2 30 1 2 2 3510/6/2008 CSE 5311 Fall 2007M Kumar9Procedure LCS(x,y)Input : The lists x and yOutput : The longest common subsequence and its length1. for j ← 0 to n do2. L[0,j] ← 0;3. for i ← 1 to m do4. L[i,0] ←0; 5. for j ← 1 to n do6. if a[i] ≠ b[j] then7. L[i,j] ← max {L[i-1,j],L[i,j-1]};8. else9 L[i,j] ← 1+L[i-1,j-1];10/6/2008 CSE 5311 Fall 2007M Kumar10Example:Consider, lists x = abcabba and y = cbabac1233334111222301112220000001223334001111112223330 0 000000cababc654321000 a b c a b b a610/6/2008 CSE 5311 Fall 2007M Kumar11Consider another exampleabaacbacab and bacabbcaba LCS : bacacab1 2 3 4 5 5 5 6 7 71 2 3 4 4 4 5 6 6 661 2 3 4 4 4 5 5 5 61 2 3 3 4 4 4 41 2 3 4 4 4 4 5 55 51 2 3 3 3 3 4 4 4 41 2 2 3 3 3 3 3 3 41 2 2 2 2 2 2 3 3 31 1 1 1 2 2 2 2 2 20 1 1 1 1 1 1 1 1 1`0000000000bacabcaaba0 0 0 0 0 0 0 0 0 0 0 00 b a c a b b c a b a10/6/2008 CSE 5311 Fall 2007M Kumar12• Give a dynamic-programming solution to the 0-1 knapsack problem that runs in O(nW) time, where n is the number of items and W is the maximum weight of items that the thief can put in his knapsack. The weight is measured in Kgs (say). The maximum weight is an integer.The given items are 1..nLet S be the optimal solution for W and i be the highest numbered item in S.S’ = S-{i} is an optimal solution for (W-wi) Kilos and items 1.. i-1.The value of the solution in S is the value viof item i plus the value of the solution S’.Let c[i,w] be the value of the solution for items 1..i and maximum weight w. 0if i =0 or w=0.C[i,w] =  c[i-1,w]if wi> residual w (i.e., w-wi-1)max (vi+c[i-1,w-wi] ,c[i-1,w] ) if i >0 and w ≥ wiThe value of the solution for i items either includes item i, in which case it is viplus a Subproblem solution for i-1 items and with weight excluding wior doesn’t include the item i.710/6/2008 CSE 5311 Fall 2007M Kumar13• Give a dynamic-programming solution to the 0-1 knapsack problem that runs in O(nW) time, where n is the number of items and W is the maximum weight of items that the thief can put in his knapsack. Inputs : W, n, v=<v1,v2, …, vn> and w = < w1, w2, …, wn>The table is c[0..n, 0..W] – each entry is referred to as c[i,j]The first row entries are filled first and then the second row entries are computed and so on (very similar to the LCS solution).At the end c[n,W] contains the maximum value. Trace the items which are part of the solution from c[n,W]. If c[i,w] = c[i-1,w] then i is not part of the solution, go to c[i-1,w] and trace backIf c[i,w] ≠ c[i-1,w] then i is part of the solution, trace with c[i-1,w-wi].10/6/2008 CSE 5311 Fall 2007M Kumar141524203310121221ValueWeightItem373025151004323022121003222222121002121212120010000000543210? wN=4, W = 5C[i,w] = c[i-1,w]if wi> w = max (vi+c[i-1,w-wi] ,c[i-1,w] ) if i >0 and w ≥ wiw810/6/2008 CSE 5311 Fall 2007M Kumar151524253310121221ValueWeightItem403525151004373525121003222222121002121212120010000000543210C[i,w] = c[i-1,w]if wi> w = max (vi+c[i-1,w-wi] ,c[i-1,w] ) if i >0 and w ≥ wiw10/6/2008 CSE 5311 Fall 2007M Kumar16Matrix-chain MultiplicationConsider the matrix multiplication procedureMATRIX_MULTIPLY(A,B)1. if columns[A] ≠ rows[B]2. then error "incompatible dimensions”3. else for i ←1 to rows[A]4. do for j ←1 to columns[B]5. do C[i,j] ←0;6. for k ← 1 to columns [A]7. do C[i,j] ←C[i,j]+A[i,k]*B[k,j];8. return C910/6/2008 CSE 5311 Fall 2007M Kumar17The time to compute a matrix product is dominated by the number of scalar multiplications in line 7.If matrix A is of size (p×q) and B is of size (q×r), then