4.4. Subproblem Dependency

So, we have seen earlier that if we just look blindly at every position and try to scan the word starting that position, we get something which is an order m, n square. Now, this solution when require as to fill in the table of size m time n, so obviously, every entries in the m times n table, we just have to look at a neighbors to fill it up. So, it is a constant time operation. So, m times n entries, we fill it m times n times. So, we have an order n 1, m n.

The initial part of the discussion highlights the inefficiency of naive algorithms that analyze every possible starting position in the input strings to find matches. This method has a time complexity of O(m * n), where 'm' and 'n' are the lengths of the two strings being compared. However, to optimize this process, a table of size m * n is filled based on the relationships between the characters of the two strings. This table allows for efficient lookups of matching sequences based on their neighboring entries, which further simplifies the computation and holds the process to a manageable runtime. Thus, using dynamic programming is a means to reduce complexity by using past results to help achieve current results.

Think of trying to find the best route on a map from one city to another without looking at the paths already explored. If you keep backtracking every step, it would take too long (similar to O(m * n)). Instead, by marking paths that you've already taken (like filling the table) and using that information to choose your next step intelligently, you can find your destination more efficiently.

So, we can now look at a slightly more general problem than longest common subword, which is more interesting computationally. So, what if we do not look for an exact match, but we allow a self to drop some letters. So, we have a subsequence not a subword, it allows us to drop some letters and now, if you want to know, after dropping some letters, what is the longest match we can find.

This chunk elaborates on the longest common subsequence (LCS) problem, which is an extension of the longest common subword problem. While common subword requires letters to match exactly, the LCS allows for dropping letters, meaning non-consecutive characters can form a match. This flexibility permits longer sequences to be recognized as matches. For example, if 'secret' and 'bisect' are being compared, we can drop letters to find longer matching subsequences, thereby finding relationships between the two strings that wouldn’t be apparent under strict matching rules.

Consider a puzzle where you have to form a word using a selection of letters. If you're allowed to skip letters, you could still say the letters form words even if ingredients are missing. Think of 'dinosaur' and 'sandstorm'; dropping certain letters will allow for longer matches even though not all letters are utilized directly.

So, before we proceed it useful to look at why the longest common subsequence problem is interesting. One of the area is an bioinformatics. So, biologists are interested in identifying how close two species are each other in a genetic sense.

This chunk discusses the significance of the longest common subsequence in real-world applications, particularly in bioinformatics. By comparing DNA strings, biologists can evaluate species' similarities and differences by identifying common genetic sequences. The LCS allows researchers to determine how much of the sequences align, even with variations, indicating evolutionary relationships. Identifying these relationships is crucial for understanding biodiversity and the mechanisms of evolution.

Imagine comparing two family trees. Even if the trees have branches (extra variations or genes), you can still trace back shared ancestors by recognizing common connections. Similarly, the LCS helps biologists find shared traits in genetic sequences despite mutations and extra genes in different species.

So, let us try understanding inductive structure of this longest common subsequence problem directly, not throw the longest common subword. So, the first thing to note is that if I am looking for this longest common subword between these two, supposing I find that a 0, in fact equal to b 0.

This section introduces the inductive approach to solving the LCS problem. The idea is that if two characters from the strings are the same (let’s say a[i] equals b[j]), they form part of the solution. The problem then reduces to finding the LCS of the remaining substrings. If they aren’t equal, however, we must explore two potential subproblems (dropping one character and keeping the other). The beauty of this approach is that it allows for systematic exploration of all possibilities without redundantly examining every combination, which leads to a more efficient solution.

Think of a detective trying to piece together a timeline of events. If they know a certain event happened at a specific time (equivalent to matching characters), they can focus on the events that come before and after that match. If an event conflicts with it, the detective can look at two alternate theories based on what events could have happened next, narrowing down possibilities.

--