This is a discrete math problem. Some knowledge of dynamic programming and/or co

Question

This is a discrete math problem. Some knowledge of dynamic programming and/or computer science may help.

given two strings z = z122 . .. zn and y = yiy2 Um, we can find the longest common substring. For example, if z = 9, 2, 8, 3, 7,4, 1 and y = 2.3, 9, 6, 8, 5, 7, 1,4 then the longest common substring is 9,8,7,1. However, suppose we want to compute the longest one that is also increasing, which in this case would be 2,3,4. Design an algorithm to compute this (a) Design the algorithm. (b) Prove your algorithm is correct. (c) Analyze t

Explanation / Answer

Algorithm using Dynamic programming:

let X=<x1,x2,.......vm> and Y=<y1,y2.......yn> be sequences, and let Z=<z1,z2,......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 6=yn,then zk 6=xm implies that Z is an LCS of Xm-1 and Y.

3.If xm 6=yn,then zk 6=yn implis that Z is an LCS of X and Yn-1.

Proof

1.if zk xm,then we could append xm=yn to Z to obtain a common subsequence of X and Y of length k+1,contradicting the supposition that Z is a longest common subsequence of X and Y. Thus, we must have zk=xm=yn. Now, the prefix Zk-1 is a length -(k-1) commonsequence of Xm-1 and Yn-1. We wish to see that it is an LCS. Suppose for the purpose of contracdiction that there is a common subsequence W of Xm-1 and Yn-1 with length is greater than k,which is a contradiction.

2.If zk 6=xm,then Z is a common subsequence of Xm-1 and y.if there were a common subsequence W and Xm-1 and Y with length greater than k ,then W would also be a common subsequence of Xm and Y ,contradicting the assumption that Z is an LCS of X and Y.

3. The proof is symmetric to the previous case.

Run time:

m <--length[X]

n <--length[Y]

Run time=mxn

If both sequences are of equal lenth then runtime is O(n^2)

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.