Typst Test 发布于 2024-08-03 # 笔记 Question 11.Based on this condition, we have:𝑓1(𝑗)={𝑎1,1𝑗=1min(𝑓1[𝑗−1]+𝑎1,𝑗,𝑓2[𝑗−1]+𝑡2,𝑗−1+𝑎1,𝑗)𝑗>1𝑓2(𝑗)={𝑎2,1𝑗=1min(𝑓2[𝑗−1]+𝑎2,𝑗,𝑓1[𝑗−1]+𝑡1,𝑗−1+𝑎2,𝑗)𝑗>1𝑓*=min(𝑓1[𝑗],𝑓2[𝑗])So:𝑓1,1=2𝑓2,1=4𝑓1=2𝑆→𝑆1,1𝑓1,2=min(2+6,4+1+6)=8𝑓2,2=min(2+2+5,4+5)=9𝑓2=8𝑆→𝑆1,1→𝑆1,2𝑓1,3=min(8+4,9+2+6)=12𝑓2,3=min(8+4+8,9+8)=17𝑓3=12𝑆→𝑆1,1→𝑆1,2→𝑆1,3𝑓1,4=min(12+8,17+1+8)=20𝑓2,4=min(12+1+4,17+4)=17𝑓4=17𝑆→𝑆1,1→𝑆1,2→𝑆1,3→𝑆2,4𝑓1[𝑗](𝑙𝑖𝑛𝑒)𝑓2[𝑗](𝑙𝑖𝑛𝑒)12(𝑆)4(𝑆)28(1)9(1→2)312(1)17(2)420(1)17(1→2)2.The minimum time is 17.3.Starting from the end, we always choose the minimum value and track back which line from. For example, from 𝑓2,4 backward isline 1, and from 𝑓1,3 backward is also line 1.So the fastest way is 𝑆1,1→𝑆1,2→𝑆1,3→𝑆2,4.Question 21.Shift table:LetterAGCTValue51422.AGCCGTGCCGTGCAGCCGTGCCGTGCAGCCGTGCCGTGCThe comparison count is 1+1+5=7.Question 31.Loop 1Loop 2abcde0∞∞∞∞abcde0−154−3ac(5)0∞5∞∞ae(4)0∞5∞4ce(-8)0∞5∞−3eb(2)0−15∞−3ed(7)0−154−3ac(5)0∞5∞∞ae(4)0∞5∞4ce(-8)0∞5∞−3eb(2)0−15∞−3ed(7)0−154−3The loop 1 is equal to the loop 2, which means all vertices attain the minimum value. So the result is shown as the loop 2.Question 41.Global alignment:AATG0−5 ←−10 ←−15 ←−20 ←A−5 ↑2 ↖−3 ↖←−8 ←−13 ←G−10 ↑−3 ↑−3 ↖−8 ←−6 ↖C−15 ↑−8 ↑−8 ↑−8 ↖−11 ↑A A T G __ A _ G C2.Local alignment:AATG00000A02 ↖2 ↖00G00002 ↖C00000A A GA A GQuestion 51.Class P includes all decision problems that can be solved within polynomial time in the worst-case scenario. Problems within Pare deemed efficient because they can be resolved within polynomial time, which is considered an acceptable timeframe.2.NP is the collection of all problems that can be confirmed or verified in polynomial time. Problems falling into “NP but notnecessarily P” are those where solutions can be checked in polynomial time, yet no polynomial-time algorithms are currentlyknown for solving them. A classic example is Sudoku; a 9x9 Sudoku is a P problem, but scaling it up to 99x99 Sudoku makes it nolonger a P problem. NP problems often deal with extensive datasets and demand a significant amount of time to tackle, makingsolving them a more formidable task.3.If a problem M is NP-hard, it means that every other problem in NP can be reduced to M in polynomial time. Additionally, if M isboth in NP and NP-hard, it is classified as NP-complete (NPC). The significance of NP-completeness lies in the fact that if you cansolve a problem in NPC, you can effectively solve all problems in NP since they can be reduced to M in polynomial time. Thisrelationship highlights the critical role of NP-complete problems as benchmarks for the complexity of problems within the NPclass.4.When we say that decision problem A is polynomial time reducible to decision problem B, or that there exists a polynomial timereduction from A to B, it means that for any input a belonging to A, we can create an input b for B in polynomial time such that ais a “yes” instance if and only if b is a “yes” instance.The NP-completeness of a problem is proven by showing that it can be reduced to a known NP-complete problem usingpolynomial-time transformations. This establishes a link between the complexity of the new problem and the complexity of NP-complete problems, providing insights into its computational difficulty within the NP class.