Dynamic ProgrammingSlide 20/1 Knapsack RecurrenceIterative Solution ExampleCompute f[5][*]Compute f[4][*]Compute f[3][*]Compute f[2][*]Compute f[1][c]TracebackSlide 15Slide 16Slide 17Slide 18Complexity Of TracebackMatrix Multiplication ChainsSlide 21Slide 22Product Of 5 MatricesFind Best Multiplication OrderAn Application3D RegistrationSlide 27Slide 28Dynamic Programming•Steps.View the problem solution as the result of a sequence of decisions.Obtain a formulation for the problem state.Verify that the principle of optimality holds.Set up the dynamic programming recurrence equations.Solve these equations for the value of the optimal solution.Perform a traceback to determine the optimal solution.Dynamic Programming•When solving the dynamic programming recurrence recursively, be sure to avoid the recomputation of the optimal value for the same problem state.•To minimize run time overheads, and hence to reduce actual run time, dynamic programming recurrences are almost always solved iteratively (no recursion).0/1 Knapsack Recurrence•If wn <= y, f(n,y) = pn.•If wn > y, f(n,y) = 0.•When i < nf(i,y) = f(i+1,y) whenever y < wi.f(i,y) = max{f(i+1,y), f(i+1,y-wi) + pi}, y >= wi.•Assume the weights and capacity are integers.•Only f(i,y)s with 1 <= i <= n and 0 <= y <= c are of interest.Iterative Solution Example•n = 5, c = 8, w = [4,3,5,6,2], p = [9,7,10,9,3]y54321f[i][y]0 1 2 3 4 5 6 7 8iCompute f[5][*]•n = 5, c = 8, w = [4,3,5,6,2], p = [9,7,10,9,3]y54321f[i][y]0 1 2 3 4 5 6 7 8i0 0 3 3 3 3 3 3 3Compute f[4][*]•n = 5, c = 8, w = [4,3,5,6,2], p = [9,8,10,9,3]y54321f[i][y]0 1 2 3 4 5 6 7 8i0 0 3 3 3 3 3 3 30 0 3 3 3 3 9 9 12f(i,y) = max{f(i+1,y), f(i+1,y-wi) + pi}, y >= wiCompute f[3][*]•n = 5, c = 8, w = [4,3,5,6,2], p = [9,8,10,9,3]y54321f[i][y]0 1 2 3 4 5 6 7 8i0 0 3 3 3 3 3 3 30 0 3 3 3 3 9 9 120 0 3 3 3 10 10 13 13f(i,y) = max{f(i+1,y), f(i+1,y-wi) + pi}, y >= wiCompute f[2][*]•n = 5, c = 8, w = [4,3,5,6,2], p = [9,8,10,9,3]y54321f[i][y]0 1 2 3 4 5 6 7 8i0 0 3 3 3 3 3 3 30 0 3 3 3 3 9 9 120 0 3 3 3 10 10 13 130 0 3 8 8 11 11 13 18f(i,y) = max{f(i+1,y), f(i+1,y-wi) + pi}, y >= wiCompute f[1][c]•n = 5, c = 8, w = [4,3,5,6,2], p = [9,8,10,9,3]y54321f[i][y]0 1 2 3 4 5 6 7 8i0 0 3 3 3 3 3 3 30 0 3 3 3 3 9 9 120 0 3 3 3 10 10 13 130 0 3 8 8 11 11 13 1818f(i,y) = max{f(i+1,y), f(i+1,y-wi) + pi}, y >= wiTraceback•n = 5, c = 8, w = [4,3,5,6,2], p = [9,8,10,9,3]y54321f[i][y]0 1 2 3 4 5 6 7 8i0 0 3 3 3 3 3 3 30 0 3 3 3 3 9 9 120 0 3 3 3 10 10 13 130 0 3 8 8 11 11 13 1818f[1][8] = f[2][8] => x1 = 0Traceback•n = 5, c = 8, w = [4,3,5,6,2], p = [9,8,10,9,3]y54321f[i][y]0 1 2 3 4 5 6 7 8i0 0 3 3 3 3 3 3 30 0 3 3 3 3 9 9 120 0 3 3 3 10 10 13 130 0 3 8 8 11 11 13 1818f[2][8] != f[3][8] => x2 = 110Traceback•n = 5, c = 8, w = [4,3,5,6,2], p = [9,8,10,9,3]y54321f[i][y]0 1 2 3 4 5 6 7 8i0 0 3 3 3 3 3 3 30 0 3 3 3 3 9 9 120 0 3 3 3 10 10 13 130 0 3 8 8 11 11 13 1818f[3][5] != f[4][5] => x3 = 10Traceback•n = 5, c = 8, w = [4,3,5,6,2], p = [9,8,10,9,3]y54321f[i][y]0 1 2 3 4 5 6 7 8i0 3 3 3 3 3 3 30 0 3 3 3 3 9 9 120 0 3 3 3 10 10 13 130 0 3 8 8 11 11 13 1818f[4][0] = f[5][0] => x4 = 00Traceback•n = 5, c = 8, w = [4,3,5,6,2], p = [9,8,10,9,3]y54321f[i][y]0 1 2 3 4 5 6 7 8i0 0 3 3 3 3 3 3 30 0 3 3 3 3 9 9 120 0 3 3 3 10 10 13 130 0 3 8 8 11 11 13 1818f[5][0] = 0 => x5 = 0Complexity Of Traceback•O(n)Matrix Multiplication Chains•Multiply an m x n matrix A and an n x p matrix B to get an m x p matrix C.k = 1nC(i,j) =A(i,k) * B(k,j)•We shall use the number of multiplications as our complexity measure.•n multiplications are needed to compute one C(i,j).•mnp multiplicatons are needed to compute all mp terms of C.Matrix Multiplication Chains•Suppose that we are to compute the product X*Y*Z of three matrices X, Y and Z.•The matrix dimensions are:X:(100 x 1), Y:(1 x 100), Z:(100 x 1)•Multiply X and Y to get a 100 x 100 matrix T.100 * 1 * 100 = 10,000 multiplications.•Multiply T and Z to get the 100 x 1 answer.100 * 100 * 1 = 10,000 multiplications.•Total cost is 20,000 multiplications.•10,000 units of space are needed for T.Matrix Multiplication Chains•The matrix dimensions are:X:(100 x 1)Y:(1 x 100)Z:(100 x 1)•Multiply Y and Z to get a 1 x 1 matrix T.1 * 100 * 1 = 100 multiplications.•Multiply X and T to get the 100 x 1 answer.100 * 1 * 1 = 100 multiplications.•Total cost is 200 multiplications.•1 unit of space is needed for T.Product Of 5 Matrices•Some of the ways in which the product of 5 matrices may be computed.A*(B*(C*(D*E))) right to left(((A*B)*C)*D)*E left to right(A*B)*((C*D)*E)(A*B)*(C*(D*E))(A*(B*C))*(D*E)((A*B)*C)*(D*E)Find Best Multiplication Order•Number of ways to compute the product of q matrices is O(4q/q1.5). • Evaluating all ways to compute the product takes O(4q/q0.5) time.An Application•Registration of pre- and post-operative 3D brain MRI images to determine volume of removed tumor.3D Registration3D Registration•Each image has 256 x 256 x 256 voxels.•In each iteration of the registration algorithm, the product of three matrices is computed at each voxel … (12 x 3) * (3 x 3) * (3 x 1)•Left to right computation => 12 * 3 * 3 + 12 * 3*1 = 144 multiplications per voxel per iteration.•100 iterations to converge.3D Registration•Total number of multiplications is about 2.4 * 1011.•Right to left computation => 3 * 3*1 + 12 * 3 * 1 = 45 multiplications per voxel per iteration.•Total number of multiplications is about 7.5 * 1010.•With 108 multiplications per second, time is 40 min vs 12.5