{"version":"1.0","provider_name":"Camdemy1.0","provider_url":"http:\/\/media.usc.edu.tw","title":"alg0526","description":"","author_name":null,"author_url":"http:\/\/media.usc.edu.tw\/user\/","thumbnail_url":"http:\/\/media.usc.edu.tw\/sysdata\/doc\/3\/33bb079670023f27\/thumb_l.jpg","thumbnail_height":360,"thumbnail_width":640,"html":"<iframe width='720' height='405' id='ccShare3599' frameborder='0'  src='http:\/\/media.usc.edu.tw\/media\/e\/3599' allowfullscreen><\/iframe>","type":"video","width":720,"height":405,"duration":"1:40:53","index":{"item_1":{"title":"index 1","time":"0","indent":"0","sn":"1"},"item_2":{"title":"Tracing Back in the LCS Algorithm","time":"918631","indent":"0","sn":"2"},"item_3":{"title":"** after Chapter7.ppt","time":"1424592","indent":"0","sn":"3"},"item_4":{"title":"The dynamic programming approach for solving the LCS problem:Time complexity: O(mn)","time":"1770822","indent":"0","sn":"4"},"item_5":{"title":"Tracing Back in the LCS Algorithm","time":"1926354","indent":"0","sn":"5"},"item_6":{"title":"The dynamic programming approach for solving the LCS problem:Time complexity: O(mn)","time":"1939321","indent":"0","sn":"6"},"item_7":{"title":"Tracing Back in the LCS Algorithm","time":"1940054","indent":"0","sn":"7"},"item_8":{"title":"** after Chapter7.ppt","time":"1948554","indent":"0","sn":"8"},"item_9":{"title":"Tracing Back in the LCS Algorithm","time":"1957320","indent":"0","sn":"9"},"item_10":{"title":"** after Chapter7.ppt","time":"2416983","indent":"0","sn":"10"},"item_11":{"title":"Fibonacci Sequence","time":"2507882","indent":"0","sn":"11"},"item_12":{"title":"Dynamic Programming","time":"2625780","indent":"0","sn":"12"},"item_13":{"title":"The Shortest Path","time":"2626380","indent":"0","sn":"13"},"item_14":{"title":"The Shortest Path in Multi-stage Graphs","time":"2627447","indent":"0","sn":"14"},"item_15":{"title":"Dynamic Programming Approach","time":"2629814","indent":"0","sn":"15"},"item_16":{"title":"d(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    ","time":"2692346","indent":"0","sn":"16"},"item_17":{"title":"Backward Approach (Forward Reasoning)","time":"2692980","indent":"0","sn":"17"},"item_18":{"title":"Slide 9","time":"2693646","indent":"0","sn":"18"},"item_19":{"title":"Principle of Optimality","time":"2694280","indent":"0","sn":"19"},"item_20":{"title":"Dynamic Programming","time":"2695046","indent":"0","sn":"20"},"item_21":{"title":"The Resource Allocation Problem","time":"2695480","indent":"0","sn":"21"},"item_22":{"title":"The Multi-Stage Graph Solution","time":"2696180","indent":"0","sn":"22"},"item_23":{"title":"The Resource Allocation Problem","time":"2705846","indent":"0","sn":"23"},"item_24":{"title":"The Multi-Stage Graph Solution","time":"2771512","indent":"0","sn":"24"},"item_25":{"title":"Slide 14","time":"3013510","indent":"0","sn":"25"},"item_26":{"title":"The Longest Common Subsequence (LCS) problem","time":"3014210","indent":"0","sn":"26"},"item_27":{"title":"The LCS Algorithm","time":"3015277","indent":"0","sn":"27"},"item_28":{"title":"The dynamic programming approach for solving the LCS problem:Time complexity: O(mn)","time":"3099976","indent":"0","sn":"28"},"item_29":{"title":"Tracing Back in the LCS Algorithm","time":"3162742","indent":"0","sn":"29"},"item_30":{"title":"The Two-Sequence Alignment Problem","time":"3165642","indent":"0","sn":"30"},"item_31":{"title":"Let 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 \u201c-\u201c, f(x, y)= -1. e.g.A= a  b  c  dB= c  b  -  dThe total score of the alignment is 1+ 2 \u2013 1 + 2 = 4.","time":"3208008","indent":"0","sn":"31"},"item_32":{"title":"Let Ai,j denote the optimal alignment score between a1 a2 \uf0bc ai and b1 b2 \uf0bc bj and, where 1\uf0a3 i\uf0a3 m and 1\uf0a3 j \uf0a3 n.Then, Ai,j can be expressed as follows: Ai,0 : a1 a2 \uf0bc ai are all aligned with \u201c-\u201d. A0,j : b1 b2 \uf0bc bj are all aligned with \u201c-\u201d.f(ai ,-): ai is al","time":"3213308","indent":"0","sn":"32"},"item_33":{"title":"The Ai,j\u2019s for A = a b d a d and B = b a c d  using the above recursive formula are listed below:","time":"3221508","indent":"0","sn":"33"},"item_34":{"title":"In 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 \u201c-\u201d, An arrow from (ai,bj) to (ai,bj-1): bj matched with \u201c-\u201d. Based upon the","time":"3224708","indent":"0","sn":"34"},"item_35":{"title":"Edit Distance","time":"3227141","indent":"0","sn":"35"},"item_36":{"title":"For exampleLet A = GTAAHTY and B = TAHHYC(1) Delete the first character G of A.         GTAAHTY \u2192 TAAHTY(2) Substitute the third character of A by H.TAAHTY \u2192 TAHHTY(3) Delete the fifth character of A.TAHHTY \u2192 TAHHY(4) Insert C after the last character of ","time":"3229308","indent":"0","sn":"36"},"item_37":{"title":"Slide 26","time":"3233841","indent":"0","sn":"37"},"item_38":{"title":"The RNA Maximum Base Pair Matching Problem","time":"3241274","indent":"0","sn":"38"},"item_39":{"title":"E.g.The primary structure of an RNA, R:  A\u2013G\u2013G\u2013C\u2013C\u2013U\u2013U\u2013C\u2013C\u2013USix possible secondary structures of RNA, R:","time":"3329273","indent":"0","sn":"39"},"item_40":{"title":"An RNA sequence will be represented as a string of n characters R = r1r2 \u00b7 \u00b7 \u00b7rn, where ri {A, C, G, U}. A secondary structure of R is a set S of base pairs (ri, rj), where 1 \uf0a3 i < j \uf0a3 n.(1) j - i > t, where t is a small positive constant. Typically, t = ","time":"3747569","indent":"0","sn":"40"},"item_41":{"title":"Dynamic Programming","time":"3752069","indent":"0","sn":"41"},"item_42":{"title":"To compute Mi,j, where j- i > 3, we consider the following cases from rj\u2019s 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.","time":"3757369","indent":"0","sn":"42"},"item_43":{"title":"Case 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.","time":"3760302","indent":"0","sn":"43"},"item_44":{"title":"Case 3: In the optimal solution, rj is paired with some rk, where i + 1 \uf0a3 k \uf0a3 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.","time":"3761002","indent":"0","sn":"44"},"item_45":{"title":"Find 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 \u2266 3, then Mi,j = 0. If j - i > 3, then","time":"3761769","indent":"0","sn":"45"},"item_46":{"title":"Slide 35","time":"3762236","indent":"0","sn":"46"},"item_47":{"title":"Algorithm to Compute M1,n","time":"3770302","indent":"0","sn":"47"},"item_48":{"title":"Slide 37","time":"3772269","indent":"0","sn":"48"},"item_49":{"title":"0\/1 Knapsack Problem","time":"3772869","indent":"0","sn":"49"},"item_50":{"title":"The Multi-Stage Graph Solution","time":"4086632","indent":"0","sn":"50"},"item_51":{"title":"0\/1 Knapsack Problem","time":"4144932","indent":"0","sn":"51"},"item_52":{"title":"The Multi-Stage Graph Solution","time":"4150465","indent":"0","sn":"52"},"item_53":{"title":"The Dynamic Programming Approach","time":"4232698","indent":"0","sn":"53"},"item_54":{"title":"The Multi-Stage Graph Solution","time":"4239464","indent":"0","sn":"54"},"item_55":{"title":"The Dynamic Programming Approach","time":"4253031","indent":"0","sn":"55"},"item_56":{"title":"Optimal Binary Search Trees","time":"4254131","indent":"0","sn":"56"},"item_57":{"title":"Optimal Binary Search Trees","time":"4359730","indent":"0","sn":"57"},"item_58":{"title":"Identifiers : 4, 5, 8, 10, 11, 12, 14Internal node: successful search, Pi External node: unsuccessful search, Qi","time":"4453362","indent":"0","sn":"58"},"item_59":{"title":"Optimal Binary Search Trees","time":"4610861","indent":"0","sn":"59"},"item_60":{"title":"Optimal Binary Search Trees","time":"4611361","indent":"0","sn":"60"},"item_61":{"title":"Optimal Binary Search Trees","time":"4622394","indent":"0","sn":"61"},"item_62":{"title":"Identifiers : 4, 5, 8, 10, 11, 12, 14Internal node: successful search, Pi External node: unsuccessful search, Qi","time":"4623160","indent":"0","sn":"62"},"item_63":{"title":"The Dynamic Programming Approach","time":"4715960","indent":"0","sn":"63"},"item_64":{"title":"Identifiers : 4, 5, 8, 10, 11, 12, 14Internal node: successful search, Pi External node: unsuccessful search, Qi","time":"4916258","indent":"0","sn":"64"},"item_65":{"title":"Optimal Binary Search Trees","time":"4917158","indent":"0","sn":"65"},"item_66":{"title":"Optimal Binary Search Trees","time":"4917924","indent":"0","sn":"66"},"item_67":{"title":"Optimal Binary Search Trees","time":"4931424","indent":"0","sn":"67"},"item_68":{"title":"Identifiers : 4, 5, 8, 10, 11, 12, 14Internal node: successful search, Pi External node: unsuccessful search, Qi","time":"4933024","indent":"0","sn":"68"},"item_69":{"title":"The Dynamic Programming Approach","time":"4933624","indent":"0","sn":"69"},"item_70":{"title":"General Formula","time":"4973724","indent":"0","sn":"70"},"item_71":{"title":"Computation Relationships of Subtrees","time":"5116022","indent":"0","sn":"71"},"item_72":{"title":"General Formula","time":"5175255","indent":"0","sn":"72"},"item_73":{"title":"The Dynamic Programming Approach","time":"5178588","indent":"0","sn":"73"},"item_74":{"title":"Identifiers : 4, 5, 8, 10, 11, 12, 14Internal node: successful search, Pi External node: unsuccessful search, Qi","time":"5179622","indent":"0","sn":"74"},"item_75":{"title":"The Dynamic Programming Approach","time":"5191088","indent":"0","sn":"75"},"item_76":{"title":"General Formula","time":"5320853","indent":"0","sn":"76"},"item_77":{"title":"Computation Relationships of Subtrees","time":"5321820","indent":"0","sn":"77"},"item_78":{"title":"General Formula","time":"5369953","indent":"0","sn":"78"},"item_79":{"title":"Computation Relationships of Subtrees","time":"5384053","indent":"0","sn":"79"},"item_80":{"title":"General Formula","time":"5442019","indent":"0","sn":"80"},"item_81":{"title":"Computation Relationships of Subtrees","time":"5457585","indent":"0","sn":"81"},"item_82":{"title":"General Formula","time":"5830315","indent":"0","sn":"82"},"item_83":{"title":"The Dynamic Programming Approach","time":"5830815","indent":"0","sn":"83"},"item_84":{"title":"Identifiers : 4, 5, 8, 10, 11, 12, 14Internal node: successful search, Pi External node: unsuccessful search, Qi","time":"5938081","indent":"0","sn":"84"},"item_85":{"title":"Optimal Binary Search Trees","time":"5938914","indent":"0","sn":"85"},"item_86":{"title":"Optimal Binary Search Trees","time":"5940247","indent":"0","sn":"86"},"item_87":{"title":"Optimal Binary Search Trees","time":"5969447","indent":"0","sn":"87"},"item_88":{"title":"Identifiers : 4, 5, 8, 10, 11, 12, 14Internal node: successful search, Pi External node: unsuccessful search, Qi","time":"5969880","indent":"0","sn":"88"},"item_89":{"title":"Optimal Binary Search Trees","time":"5970847","indent":"0","sn":"89"},"item_90":{"title":"Optimal Binary Search Trees","time":"5976480","indent":"0","sn":"90"},"item_91":{"title":"The Dynamic Programming Approach","time":"5977447","indent":"0","sn":"91"},"item_92":{"title":"The Multi-Stage Graph Solution","time":"5979414","indent":"0","sn":"92"},"item_93":{"title":"0\/1 Knapsack Problem","time":"5982947","indent":"0","sn":"93"},"item_94":{"title":"Slide 37","time":"5983980","indent":"0","sn":"94"},"item_95":{"title":"Algorithm to Compute M1,n","time":"5984480","indent":"0","sn":"95"},"item_96":{"title":"Slide 35","time":"5985447","indent":"0","sn":"96"},"item_97":{"title":"Find 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 \u2266 3, then Mi,j = 0. If j - i > 3, then","time":"5986980","indent":"0","sn":"97"},"item_98":{"title":"Case 3: In the optimal solution, rj is paired with some rk, where i + 1 \uf0a3 k \uf0a3 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.","time":"5987947","indent":"0","sn":"98"},"item_99":{"title":"Case 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.","time":"5988947","indent":"0","sn":"99"},"item_100":{"title":"To compute Mi,j, where j- i > 3, we consider the following cases from rj\u2019s 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.","time":"5989980","indent":"0","sn":"100"},"item_101":{"title":"Dynamic Programming","time":"5990947","indent":"0","sn":"101"},"item_102":{"title":"An RNA sequence will be represented as a string of n characters R = r1r2 \u00b7 \u00b7 \u00b7rn, where ri {A, C, G, U}. A secondary structure of R is a set S of base pairs (ri, rj), where 1 \uf0a3 i < j \uf0a3 n.(1) j - i > t, where t is a small positive constant. Typically, t = ","time":"5991980","indent":"0","sn":"102"},"item_103":{"title":"E.g.The primary structure of an RNA, R:  A\u2013G\u2013G\u2013C\u2013C\u2013U\u2013U\u2013C\u2013C\u2013USix possible secondary structures of RNA, R:","time":"5992480","indent":"0","sn":"103"},"item_104":{"title":"The RNA Maximum Base Pair Matching Problem","time":"5993447","indent":"0","sn":"104"},"item_105":{"title":"Slide 26","time":"5994447","indent":"0","sn":"105"},"item_106":{"title":"For exampleLet A = GTAAHTY and B = TAHHYC(1) Delete the first character G of A.         GTAAHTY \u2192 TAAHTY(2) Substitute the third character of A by H.TAAHTY \u2192 TAHHTY(3) Delete the fifth character of A.TAHHTY \u2192 TAHHY(4) Insert C after the last character of ","time":"6008480","indent":"0","sn":"106"},"item_107":{"title":"Edit Distance","time":"6008913","indent":"0","sn":"107"},"item_108":{"title":"In 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 \u201c-\u201d, An arrow from (ai,bj) to (ai,bj-1): bj matched with \u201c-\u201d. Based upon the","time":"6009947","indent":"0","sn":"108"},"item_109":{"title":"The Ai,j\u2019s for A = a b d a d and B = b a c d  using the above recursive formula are listed below:","time":"6010413","indent":"0","sn":"109"},"item_110":{"title":"Let Ai,j denote the optimal alignment score between a1 a2 \uf0bc ai and b1 b2 \uf0bc bj and, where 1\uf0a3 i\uf0a3 m and 1\uf0a3 j \uf0a3 n.Then, Ai,j can be expressed as follows: Ai,0 : a1 a2 \uf0bc ai are all aligned with \u201c-\u201d. A0,j : b1 b2 \uf0bc bj are all aligned with \u201c-\u201d.f(ai ,-): ai is al","time":"6010913","indent":"0","sn":"110"},"item_111":{"title":"Let 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 \u201c-\u201c, f(x, y)= -1. e.g.A= a  b  c  dB= c  b  -  dThe total score of the alignment is 1+ 2 \u2013 1 + 2 = 4.","time":"6011413","indent":"0","sn":"111"},"item_112":{"title":"The Two-Sequence Alignment Problem","time":"6011947","indent":"0","sn":"112"},"item_113":{"title":"Tracing Back in the LCS Algorithm","time":"6012447","indent":"0","sn":"113"},"item_114":{"title":"The dynamic programming approach for solving the LCS problem:Time complexity: O(mn)","time":"6012947","indent":"0","sn":"114"},"item_115":{"title":"The LCS Algorithm","time":"6014880","indent":"0","sn":"115"},"item_116":{"title":"The Longest Common Subsequence (LCS) problem","time":"6028513","indent":"0","sn":"116"},"item_117":{"title":"Slide 14","time":"6029413","indent":"0","sn":"117"},"item_118":{"title":"The Multi-Stage Graph Solution","time":"6030380","indent":"0","sn":"118"},"item_119":{"title":"The Resource Allocation Problem","time":"6034913","indent":"0","sn":"119"},"item_120":{"title":"Dynamic Programming","time":"6036380","indent":"0","sn":"120"},"item_121":{"title":"Principle of Optimality","time":"6036880","indent":"0","sn":"121"},"item_122":{"title":"Slide 9","time":"6037913","indent":"0","sn":"122"},"item_123":{"title":"Backward Approach (Forward Reasoning)","time":"6039446","indent":"0","sn":"123"},"item_124":{"title":"d(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    ","time":"6039980","indent":"0","sn":"124"},"item_125":{"title":"Dynamic Programming Approach","time":"6040480","indent":"0","sn":"125"},"item_126":{"title":"The Shortest Path in Multi-stage Graphs","time":"6040980","indent":"0","sn":"126"},"item_127":{"title":"The Shortest Path","time":"6041513","indent":"0","sn":"127"},"item_128":{"title":"Dynamic Programming","time":"6042013","indent":"0","sn":"128"},"item_129":{"title":"Fibonacci Sequence","time":"6042513","indent":"0","sn":"129"},"item_130":{"title":"Chapter 7","time":"6043046","indent":"0","sn":"130"},"item_131":{"title":"** after Chapter7.ppt","time":"6050646","indent":"0","sn":"131"},"item_132":{"title":"alg0526","time":"6053013","indent":"0","sn":"132"}},"resolution":{"playtype":"fs","subtype":"","src":"1920x1080","mp4":"720x404","mp4_hd":"1280x720","mp4_4k":"","mp4_1920":"1920x1080","mp4_src":"","mp4_base":""},"base_image":{"thumb":"http:\/\/media.usc.edu.tw\/sysdata\/doc\/3\/33bb079670023f27\/thumb.jpg","cover":"http:\/\/media.usc.edu.tw\/sysdata\/doc\/3\/33bb079670023f27\/cover.jpg","storyboard":"http:\/\/media.usc.edu.tw\/sysdata\/doc\/3\/33bb079670023f27\/video\/thumbs\/storyboard.jpg"},"srcFrom":"","base_url":"http:\/\/media.usc.edu.tw\/sysdata\/doc\/3\/33bb079670023f27","status":true}