4.9 Longest Common Subsequence (LCS) - Recursion and Dynamic Programming

hi the topic is longest common sub sequence in short lcs in this video I will explain what is the problem (LCS problem) then I will solve it using recursion I will write an algorithm and show you how it can be solved using recursion Then Recursion are time consuming So to save the time We can use memoisation 'e' has appeared here then 'c' should be following that 'e' not at that backside of 'e' instead of starting from 'e', I will start from 'c' yes, matching. 'd'- yes matching. 'g' and 'i' - yes. c-d-g-i is also there sub-sequence I'll take one more example and show you which are the same length yes there can be multiple sub-sequences of the same length also so that's it- the problem is finding whether the set of characters in these two strings are matching or not and 'A' This is one call where Otherwise- one more is trace the other nodes also they are not the same A[1] and B[3] and this is d,d and here it is 1 + A[2] and B[4] exponential time-taking algorithm this is a top-down approach here- there is an overlapping problem to improve recursion you can take the help of memoization overlapping, but if a problem is big with a lot of branches will be overlapping. So let us finally understand how memoization can make this algorithm faster. I will not change the code a table and show you how memoization can help this one. for memoization and I have taken the indexes from 0, onwards. Now let us see how this algorithm can utilize this table to work faster. So first we will start from [0,0], then [1,0], then [2,1] no- they are not matching so take the maximum of these two. This condition. So- that is 0,0 is 0 Then B is matching with this one. Yes- matching. 0 + 1 ... 1 then B and D they are not matching so previous column with previous row- here - maximum of this that is 1 only. Now next row maximum of these two and the maximum of these two is 2. N is matching here add one two so when there's a match, take the diagonal add one then E previous column, previous row - two. previous column, previous row - two. Now here, E is matching with this one LCS algorithm using dynamic programming is m cross n that's it the matching characters need not be continuous and you can reduce its time. D A Not matching. E is matching here

Channel: Abdul Bari

Views: 832,219

Keywords: LCS, longets common subsequence, dynamic programming, memoization, recursion, algorithms, abdul bari, bari, gate

Id: sSno9rV8Rhg

Length: 23min 35sec (1415 seconds)

Published: Thu Apr 19 2018