alg0526

1.0Camdemy1.0http://media.usc.edu.twalg0526http://media.usc.edu.tw/user/http://media.usc.edu.tw/sysdata/doc/3/33bb079670023f27/thumb_l.jpg360640<iframe width='720' height='405' id='ccShare3599' frameborder='0' src='http://media.usc.edu.tw/media/e/3599' allowfullscreen></iframe>video7204051:40:53index 1001Tracing Back in the LCS Algorithm91863102** after Chapter7.ppt142459203The dynamic programming approach for solving the LCS problem:Time complexity: O(mn)177082204Tracing Back in the LCS Algorithm192635405The dynamic programming approach for solving the LCS problem:Time complexity: O(mn)193932106Tracing Back in the LCS Algorithm194005407** after Chapter7.ppt194855408Tracing Back in the LCS Algorithm195732009** after Chapter7.ppt2416983010Fibonacci Sequence2507882011Dynamic Programming2625780012The Shortest Path2626380013The Shortest Path in Multi-stage Graphs2627447014Dynamic Programming Approach2629814015d(B, T) = min{9+d(D, T), 5+d(E, T), 16+d(F, T)} = min{9+18, 5+13, 16+2} = 18.d(C, T) = min{ 2+d(F, T) } = 2+2 = 4d(S, T) = min{1+d(A, T), 2+d(B, T), 5+d(C, T)} = min{1+22, 2+18, 5+4} = 9. The above way of reasoning is called 2692346016Backward Approach (Forward Reasoning)2692980017Slide 92693646018Principle of Optimality2694280019Dynamic Programming2695046020The Resource Allocation Problem2695480021The Multi-Stage Graph Solution2696180022The Resource Allocation Problem2705846023The Multi-Stage Graph Solution2771512024Slide 143013510025The Longest Common Subsequence (LCS) problem3014210026The LCS Algorithm3015277027The dynamic programming approach for solving the LCS problem:Time complexity: O(mn)3099976028Tracing Back in the LCS Algorithm3162742029The Two-Sequence Alignment Problem3165642030Let f(x, y) denote the score for aligning x with y. If x and y are the same, f(x, y)= 2.If x and y are not the same, f(x, y)= 1.If x or y is “-“, f(x, y)= -1. e.g.A= a b c dB= c b - dThe total score of the alignment is 1+ 2 – 1 + 2 = 4.3208008031Let Ai,j denote the optimal alignment score between a1 a2  ai and b1 b2  bj and, where 1 i m and 1 j  n.Then, Ai,j can be expressed as follows: Ai,0 : a1 a2  ai are all aligned with “-”. A0,j : b1 b2  bj are all aligned with “-”.f(ai ,-): ai is al3213308032The Ai,j’s for A = a b d a d and B = b a c d using the above recursive formula are listed below:3221508033In the above table, we have also recorded how each Ai,j is obtained.An arrow from (ai,bj) to (ai-1,bj-1): ai matched with bj. An arrow from (ai,bj) to (ai-1,bj): ai matched with “-”, An arrow from (ai,bj) to (ai,bj-1): bj matched with “-”. Based upon the3224708034Edit Distance3227141035For exampleLet A = GTAAHTY and B = TAHHYC(1) Delete the first character G of A. GTAAHTY → TAAHTY(2) Substitute the third character of A by H.TAAHTY → TAHHTY(3) Delete the fifth character of A.TAHHTY → TAHHY(4) Insert C after the last character of 3229308036Slide 263233841037The RNA Maximum Base Pair Matching Problem3241274038E.g.The primary structure of an RNA, R: A–G–G–C–C–U–U–C–C–USix possible secondary structures of RNA, R:3329273039An RNA sequence will be represented as a string of n characters R = r1r2 · · ·rn, where ri {A, C, G, U}. A secondary structure of R is a set S of base pairs (ri, rj), where 1  i < j  n.(1) j - i > t, where t is a small positive constant. Typically, t = 3747569040Dynamic Programming3752069041To compute Mi,j, where j- i > 3, we consider the following cases from rj’s point of view. Case 1: In the optimal solution, rj is not paired with any other base. In this case, find an optimal solution for riri+1 . . . rj-1 and Mi,j =Mi,j-1.3757369042Case 2: In the optimal solution, rj is paired with ri. In this case, find an optimal solution for ri+1ri+2 . . . rj-1 and Mi,j = 1 + Mi+1,j-1.3760302043Case 3: In the optimal solution, rj is paired with some rk, where i + 1  k  j - 4. In this case, find the optimal solutions for riri+1 . . . rk-1 and rk+1rk+1 . . . rj-1 and Mi,j = 1 + Mi,k-i+ Mk+1,j-1.3761002044Find the k between i+1 and j+ 4 such that Mi,j is the maximum, we have Compute Mi,j by the following recursive formula If j - i ≦ 3, then Mi,j = 0. If j - i > 3, then3761769045Slide 353762236046Algorithm to Compute M1,n3770302047Slide 3737722690480/1 Knapsack Problem3772869049The Multi-Stage Graph Solution40866320500/1 Knapsack Problem4144932051The Multi-Stage Graph Solution4150465052The Dynamic Programming Approach4232698053The Multi-Stage Graph Solution4239464054The Dynamic Programming Approach4253031055Optimal Binary Search Trees4254131056Optimal Binary Search Trees4359730057Identifiers : 4, 5, 8, 10, 11, 12, 14Internal node: successful search, Pi External node: unsuccessful search, Qi4453362058Optimal Binary Search Trees4610861059Optimal Binary Search Trees4611361060Optimal Binary Search Trees4622394061Identifiers : 4, 5, 8, 10, 11, 12, 14Internal node: successful search, Pi External node: unsuccessful search, Qi4623160062The Dynamic Programming Approach4715960063Identifiers : 4, 5, 8, 10, 11, 12, 14Internal node: successful search, Pi External node: unsuccessful search, Qi4916258064Optimal Binary Search Trees4917158065Optimal Binary Search Trees4917924066Optimal Binary Search Trees4931424067Identifiers : 4, 5, 8, 10, 11, 12, 14Internal node: successful search, Pi External node: unsuccessful search, Qi4933024068The Dynamic Programming Approach4933624069General Formula4973724070Computation Relationships of Subtrees5116022071General Formula5175255072The Dynamic Programming Approach5178588073Identifiers : 4, 5, 8, 10, 11, 12, 14Internal node: successful search, Pi External node: unsuccessful search, Qi5179622074The Dynamic Programming Approach5191088075General Formula5320853076Computation Relationships of Subtrees5321820077General Formula5369953078Computation Relationships of Subtrees5384053079General Formula5442019080Computation Relationships of Subtrees5457585081General Formula5830315082The Dynamic Programming Approach5830815083Identifiers : 4, 5, 8, 10, 11, 12, 14Internal node: successful search, Pi External node: unsuccessful search, Qi5938081084Optimal Binary Search Trees5938914085Optimal Binary Search Trees5940247086Optimal Binary Search Trees5969447087Identifiers : 4, 5, 8, 10, 11, 12, 14Internal node: successful search, Pi External node: unsuccessful search, Qi5969880088Optimal Binary Search Trees5970847089Optimal Binary Search Trees5976480090The Dynamic Programming Approach5977447091The Multi-Stage Graph Solution59794140920/1 Knapsack Problem5982947093Slide 375983980094Algorithm to Compute M1,n5984480095Slide 355985447096Find the k between i+1 and j+ 4 such that Mi,j is the maximum, we have Compute Mi,j by the following recursive formula If j - i ≦ 3, then Mi,j = 0. If j - i > 3, then5986980097Case 3: In the optimal solution, rj is paired with some rk, where i + 1  k  j - 4. In this case, find the optimal solutions for riri+1 . . . rk-1 and rk+1rk+1 . . . rj-1 and Mi,j = 1 + Mi,k-i+ Mk+1,j-1.5987947098Case 2: In the optimal solution, rj is paired with ri. In this case, find an optimal solution for ri+1ri+2 . . . rj-1 and Mi,j = 1 + Mi+1,j-1.5988947099To compute Mi,j, where j- i > 3, we consider the following cases from rj’s point of view. Case 1: In the optimal solution, rj is not paired with any other base. In this case, find an optimal solution for riri+1 . . . rj-1 and Mi,j =Mi,j-1.59899800100Dynamic Programming59909470101An RNA sequence will be represented as a string of n characters R = r1r2 · · ·rn, where ri {A, C, G, U}. A secondary structure of R is a set S of base pairs (ri, rj), where 1  i < j  n.(1) j - i > t, where t is a small positive constant. Typically, t = 59919800102E.g.The primary structure of an RNA, R: A–G–G–C–C–U–U–C–C–USix possible secondary structures of RNA, R:59924800103The RNA Maximum Base Pair Matching Problem59934470104Slide 2659944470105For exampleLet A = GTAAHTY and B = TAHHYC(1) Delete the first character G of A. GTAAHTY → TAAHTY(2) Substitute the third character of A by H.TAAHTY → TAHHTY(3) Delete the fifth character of A.TAHHTY → TAHHY(4) Insert C after the last character of 60084800106Edit Distance60089130107In the above table, we have also recorded how each Ai,j is obtained.An arrow from (ai,bj) to (ai-1,bj-1): ai matched with bj. An arrow from (ai,bj) to (ai-1,bj): ai matched with “-”, An arrow from (ai,bj) to (ai,bj-1): bj matched with “-”. Based upon the60099470108The Ai,j’s for A = a b d a d and B = b a c d using the above recursive formula are listed below:60104130109Let Ai,j denote the optimal alignment score between a1 a2  ai and b1 b2  bj and, where 1 i m and 1 j  n.Then, Ai,j can be expressed as follows: Ai,0 : a1 a2  ai are all aligned with “-”. A0,j : b1 b2  bj are all aligned with “-”.f(ai ,-): ai is al60109130110Let f(x, y) denote the score for aligning x with y. If x and y are the same, f(x, y)= 2.If x and y are not the same, f(x, y)= 1.If x or y is “-“, f(x, y)= -1. e.g.A= a b c dB= c b - dThe total score of the alignment is 1+ 2 – 1 + 2 = 4.60114130111The Two-Sequence Alignment Problem60119470112Tracing Back in the LCS Algorithm60124470113The dynamic programming approach for solving the LCS problem:Time complexity: O(mn)60129470114The LCS Algorithm60148800115The Longest Common Subsequence (LCS) problem60285130116Slide 1460294130117The Multi-Stage Graph Solution60303800118The Resource Allocation Problem60349130119Dynamic Programming60363800120Principle of Optimality60368800121Slide 960379130122Backward Approach (Forward Reasoning)60394460123d(B, T) = min{9+d(D, T), 5+d(E, T), 16+d(F, T)} = min{9+18, 5+13, 16+2} = 18.d(C, T) = min{ 2+d(F, T) } = 2+2 = 4d(S, T) = min{1+d(A, T), 2+d(B, T), 5+d(C, T)} = min{1+22, 2+18, 5+4} = 9. The above way of reasoning is called 60399800124Dynamic Programming Approach60404800125The Shortest Path in Multi-stage Graphs60409800126The Shortest Path60415130127Dynamic Programming60420130128Fibonacci Sequence60425130129Chapter 760430460130** after Chapter7.ppt60506460131alg052660530130132fs1920x1080720x4041280x7201920x1080http://media.usc.edu.tw/sysdata/doc/3/33bb079670023f27/thumb.jpghttp://media.usc.edu.tw/sysdata/doc/3/33bb079670023f27/cover.jpghttp://media.usc.edu.tw/sysdata/doc/3/33bb079670023f27/video/thumbs/storyboard.jpghttp://media.usc.edu.tw/sysdata/doc/3/33bb079670023f271