Writing Assignment Idea By using class notes, the textbook and online resources,
ID: 3593620 • Letter: W
Question
Writing Assignment Idea By using class notes, the textbook and online resources, you will write a paper explaining the topic of Dynamic Programming Specification Write a paper that explains the concept of Dynamic Programming for each of the two problems of a classmate who knows nothing about Dynamic Programming or the two problems would be able to read and understand t. Divide the paper into 2 sections, one for each problem. Each section should have the following structure: d Longest Common Subsequence. Write the paper so that 1. Define the problem. Why is it useful to solve? (Where is it used?) 2. Size of the entire solution space. Is it n or n or better? Or is it exponential? Estimate it. No need for a proof. 3. Can it be solved by other approaches such as Brute Force, Decrement and Conquer, Divide and Conquer, Greedy Methods? If so, what would be the time and space complexity of an 4. Show the structure of the optimal solution to this problem. Give an informal (brief) 5. Based on 4, give the pseudo code for an algorithm based on the dynamic programming 6. What is the time and space complexity of your algorithm? algorithm based on those approaches? justification that the principle of optimality holds. approach. Note: 1. The first problem is discussed in the text. For the second problem, please look up online resources or other books such as Introduction to Algorithms by Cormen et. al (MIT Press) 2. Please study the material and then write in your own words. You may not copy and paste from any source. Also, cite the source that you used to understand the problem and the solution approaches.Explanation / Answer
1)The longest common subsequence (LCS) problem is the problem of finding the longest subsequence common to all sequences in a set of sequences. 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. It is a classic computer science problem, the basis of diff (a file comparison program that outputs the differences between two files), and has applications in bioinformatics.
2)In general case, problem is solved in O(n2) time, where n is the length of the input, equaling the time required for the special case of k = 1 (k is substring length). The space requirement is O(kn).This solution is exponential in term of time complexity
3)Brute Force Algorithm can be used to solve LCS
4)An optimal solution to a problem (instance) contains optimal solutions to subproblems.
Suppose we want to find LCS of two strings ( str1 of size m and str2 of size n )
The structure of an optimal solution is-:
Let lcs ( i , j ) denotes the length of LCS till index i of str1 and index j of str2.
if str1 ( i ) == str2 ( j ) , then the problem reduces to finding 1 + lcs ( i - 1 , j - 1 )
5)Recursive algorithm for LCS
LCS(x, y, i, j)
if x[i] = y[ j]
then c[i, j] ¬ LCS(x, y, i–1, j–1) + 1
else c[i, j] ¬ max{ LCS(x, y, i–1, j), LCS(x, y, i, j–1)}
Worst-case: x[i] ¹ y[ j], in which case the algorithm evaluates two subproblems, each with only one parameter decremented.
6)Time & space complexity for the above algorithm is O(mn)
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.