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.
This comment has been removed by the author.
ReplyDeleteThis comment has been removed by the author.
ReplyDeleteThis blog post on DevOps monitoring is a comprehensive guide that dives deep into best practices for continuous monitoring. It provides valuable insights on how businesses can leverage monitoring tools to enhance their DevOps processes and ensure optimal performance. The detailed explanations and practical tips make it a must-read for anyone looking to streamline their development operations successfully. Overall, this blog offers a wealth of knowledge that can help organizations improve their monitoring strategies and achieve greater efficiency in their DevOps workflows.
ReplyDelete