Dynamic Programming

Dynamic Programming is a method of solving problems exhibiting the properties of overlapping subproblems and optimal substructure that takes much less time than naive methods.It is typically applied to optimization problems.

Longest Common subsequence and substring:

Longest Common subsequence and substring are two applications of Dynamic Programming.The longest common subsequence problem is finding the longest subsequence common to all sequences in a set of sequences (often just two) while longest common substring is finding the longest substring.

1)Determine an LCS of {1,0,0,1,0,1,0,1} and {0,1,0,1,1,0,1,1,0}.
2)Give an algorithm to find the Longest common subsequence of sequences with lengths m,n respectively and also analyze their time complexities.
3)Give an algorithm to find the Longest common string of strings with lengths m,n respectively and also analyse their time complexities.
4)Give an O(n^2) time algorithm to find the longest monotonically increasing subsequence of a sequence of n numbers.
5)Give an O(n^2) time algorithm to find the longest monotonically increasing subsequence of a sequence of n numbers.
6)What is the difference between longest common subsequence and longest common substring
7)State few applications of Dynamic Programming.

No comments:

Post a Comment