its a question about algorithmreally thx for ur generous help^_^ i\'d be very ap

Question

its a question about algorithmreally thx for ur generous help^_^
i'd be very appreciate that if u can help me with all subquestions^_^

. The Longest Common Subsequence (TCS) problem of two sequences of length can be solved by a dynamic progamming in both On) time and space. . 1aThe space complexity of computing LCS can be redaced to O(n) by . b Descibe a new algorithm that can overcome this dramback in O(r2) time . c. How to compute the Longest Common Subseqaence LCS) of three . d. What is the tme complexky of using the same dynamic programing idea retaining oee a one-dimensional array dheing bottom up DP. What is the retaning oce a oae major drava back of this approach and in O(e) space sequences? Ihustrate a dynamic prograing algorihm using the following example: ABCB, BDCAB, and ABCA for compating L CS of n sequesces of length k?

Explanation / Answer

LCS Problem Statement: Given two sequences, find the length of longest subsequence present in both of them. A subsequence is a sequence that appears in the same relative order, but not necessarily contiguous. For example, “abc”, “abg”, “bdf”, “aeg”, ‘”acefg”, .. etc are subsequences of “abcdefg”. So a string of length n has 2^n different possible subsequences.

For part C the algorithm That I could suggest is First find the LCS for any two of three sequences after that apply LCS again for the result to remaining sequence to get longest subsequence.

ABCB,BDCB,ABCA --->from first two we get BC as subsequence again from BC and ABCA we get BC as the final longest LCS.

For part D the time complexity could be O(n(n1) 2) for 3 strings.

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

---

---

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