Dynamic ProgrammingLongest Common SubsequenceOther sequence questionsMore problemsSlide 5Steps in Dynamic ProgrammingSlide 7Naïve AlgorithmOptimal SubstructureSlide 10Slide 11Recursive SolutionSlide 13Slide 14Computing the length of an LCSConstructing an LCSSlide 17Slide 18Optimal Binary Search TreesExpected Search CostExampleSlide 22Slide 23Slide 24Slide 25Slide 26Slide 27Computing an Optimal SolutionPseudo-codeElements of Dynamic ProgrammingSlide 31Slide 32Optimal SubstuctureSlide 34Overlapping SubproblemsSlide 36Elements of DP AlgorithmsApplicability to Optimization ProblemsDynamic ProgrammingDynamic ProgrammingMany of the slides are from Prof. Plaisted’s resources at University of North Carolina at Chapel HillLongest Common SubsequenceProblem: Given 2 sequences, X = x1,...,xm and Y = y1,...,yn, find a common subsequence whose length is maximum. springtime ncaa tournament basketballprinting north carolina krzyzewskiSubsequence need not be consecutive, but must be in order.Other sequence questionsEdit distance: Given 2 sequences, X = x1,...,xm and Y = y1,...,yn, what is the minimum number of deletions, insertions, and changes that you must do to change one to another? Protein sequence alignment: Given a score matrix on amino acid pairs, s(a,b) for a,b{}A, and 2 amino acid sequences, X = x1,...,xmAm and Y = y1,...,ynAn, find the alignment with lowest score…More problemsOptimal BST: Given sequence K = k1 < k2 <··· < kn of n sorted keys, with a search probability pi for each key ki, build a binary search tree (BST) with minimum expected search cost.Matrix chain multiplication: Given a sequence of matrices A1 A2 … An, with Ai of dimension mini, insert parenthesis to minimize the total number of scalar multiplications.Minimum convex decomposition of a polygon,Hydrogen placement in protein structures, …Dynamic ProgrammingDynamic Programming is an algorithm design technique for optimization problems: often minimizing or maximizing.Like divide and conquer, DP solves problems by combining solutions to subproblems.Unlike divide and conquer, subproblems are not independent.»Subproblems may share subsubproblems,»However, solution to one subproblem may not affect the solutions to other subproblems of the same problem. (More on this later.)DP reduces computation by »Solving subproblems in a bottom-up fashion.»Storing solution to a subproblem the first time it is solved.»Looking up the solution when subproblem is encountered again.Key: determine structure of optimal solutionsSteps in Dynamic Programming1. Characterize structure of an optimal solution.2. Define value of optimal solution recursively.3. Compute optimal solution values either top-down with caching or bottom-up in a table.4. Construct an optimal solution from computed values.We’ll study these with the help of examples.Longest Common SubsequenceProblem: Given 2 sequences, X = x1,...,xm and Y = y1,...,yn, find a common subsequence whose length is maximum. springtime ncaa tournament basketballprinting north carolina snoeyinkSubsequence need not be consecutive, but must be in order.Naïve AlgorithmFor every subsequence of X, check whether it’s a subsequence of Y .Time: Θ(n2m).»2m subsequences of X to check.»Each subsequence takes Θ(n) time to check: scan Y for first letter, for second, and so on.Optimal SubstructureNotation:prefix Xi = x1,...,xi is the first i letters of X. This says what any longest common subsequence must look like; do you believe it?Theorem Let Z = z1, . . . , zk be any LCS of X and Y .1. If xm = yn, then zk = xm = yn and Zk-1 is an LCS of Xm-1 and Yn-1.2. If xm  yn, then either zk  xm and Z is an LCS of Xm-1 and Y .3. or zk  yn and Z is an LCS of X and Yn-1.Theorem Let Z = z1, . . . , zk be any LCS of X and Y .1. If xm = yn, then zk = xm = yn and Zk-1 is an LCS of Xm-1 and Yn-1.2. If xm  yn, then either zk  xm and Z is an LCS of Xm-1 and Y .3. or zk  yn and Z is an LCS of X and Yn-1.Optimal SubstructureProof: (case 1: xm = yn)Any sequence Z’ that does not end in xm = yn can be made longer by adding xm = yn to the end. Therefore, (1) longest common subsequence (LCS) Z must end in xm = yn. (2) Zk-1 is a common subsequence of Xm-1 and Yn-1, and (3) there is no longer CS of Xm-1 and Yn-1, or Z would not be an LCS.Theorem Let Z = z1, . . . , zk be any LCS of X and Y .1. If xm = yn, then zk = xm = yn and Zk-1 is an LCS of Xm-1 and Yn-1.2. If xm  yn, then either zk  xm and Z is an LCS of Xm-1 and Y .3. or zk  yn and Z is an LCS of X and Yn-1.Theorem Let Z = z1, . . . , zk be any LCS of X and Y .1. If xm = yn, then zk = xm = yn and Zk-1 is an LCS of Xm-1 and Yn-1.2. If xm  yn, then either zk  xm and Z is an LCS of Xm-1 and Y .3. or zk  yn and Z is an LCS of X and Yn-1.Optimal SubstructureProof: (case 2: xm  yn, and zk  xm)Since Z does not end in xm, (1) Z is a common subsequence of Xm-1 and Y, and (2) there is no longer CS of Xm-1 and Y, or Z would not be an LCS.Theorem Let Z = z1, . . . , zk be any LCS of X and Y .1. If xm = yn, then zk = xm = yn and Zk-1 is an LCS of Xm-1 and Yn-1.2. If xm  yn, then either zk  xm and Z is an LCS of Xm-1 and Y .3. or zk  yn and Z is an LCS of X and Yn-1.Theorem Let Z = z1, . . . , zk be any LCS of X and Y .1. If xm = yn, then zk = xm = yn and Zk-1 is an LCS of Xm-1 and Yn-1.2. If xm  yn, then either zk  xm and Z is an LCS of Xm-1 and Y .3. or zk  yn and Z is an LCS of X and Yn-1.Recursive SolutionDefine c[i, j] = length of LCS of Xi and Yj . We want c[m,n].. and 0, if])1,[],,1[max(, and 0, if1]1,1[,0or 0 if0],[jijiyxjijicjicyxjijicjijic. and 0, if])1,[],,1[max(, and 0, if1]1,1[,0or 0 if0],[jijiyxjijicjicyxjijicjijicThis gives a recursive algorithm and solves the problem.But does it solve it well?Recursive Solution.)end( )end( if]),[],,[max(,)end( )end( if1],[,empty or empty if0],[prefixcprefixcprefixprefixcc.)end( )end( if]),[],,[max(,)end( )end( if1],[,empty or