Winder is a new smartphone app designed to make it easier for everyone to eat their vegeta$-$bles. Vinder compares your genetic information with a large database of vegetable genetic sequences to match you with the right vegetable based on sequence similarity. Specifically, it computes the longest common subsequence between your DNA sequence and the DNA sequences of thousands of vegetables. An n$-$length DNA sequence, A$,$ is an ordered collection of elements $[$A$,$ C$,$G$,$ T$],$ or A $[$A$,$ C$,$ G$,$ T$]".$ A subsequence is a sequence formed by deleting elements from another sequence, thus preserving the original order. A k$-$length prefix of sequence A is the first k elements of A$.$ For example, A $=[$A$,$ C$,$ C$,$ G$,$ G$,$ A$,$ A$,$ T$,$ C$]$ is a sequence. $[$A$,$ C$,$ A$,$ T$]$ and $[$C$)$ are subsequences of A but $[$T$,$ Aj is not. $[$A$,$ C$,$C$,$ G$]$ is a $4-$prefix of A and $||$ is the $0-$prefix. Our goal is to find the longest common subsequence $($LCS$)$ of A$,$ the human DNA sequence, and sequences Bk D where D is the database of vegetable DNA sequences and k $=1,...,$ ID$|.$ This solution can be found efficiently using dynamic programming. At a high$-$level, the algorithm is: $1.$ For each sequence Bk D $2.$ Initialize the length of the LCS to $0.3.$ Let A; denote the ith element of A$.$ Consider each pair of A; and Bk; either Ai $=$ B: or A$,$ # B;$.$ If A; $=$ Bk$,$ then the length of the LCS of the i$-$prefix of A and j$-$prefix of Bk is one more than the LCS of the i $-1-$prefix of A and j$-1-$prefix of Bk$.$ If Ai # Bk$,$ then we cannot extend the LCS$.$ Instead, we conclude that the LCS up to $($Ai$,$ B;$)$ is the maximum of the LCS up to $($Ai$-1,$ B;$)$ or $($Ai$,$ B;$\_).$ The two aforementioned cases sum up the possibilities at $($Ai$,$ Bj$).$ We can use these to recursively define the LCS in terms of smaller problem solutions. Your goal is to describe the algorithm to do this. $1.$ Describe an algorithm to find the length of the LCS that does not use dynamic pro$-$gramming. You do not have to write pseudocode, simply describe the algorithm in enough detail so that we understand it$.$ What is the runtime? Why is it correct? You may keep your answers informal. Hint: a brute$-$force or recursive solution should have exponential runtime. CSE $3500$ Homework $02.$ Write out the recurrence relation used in the algorithm defined in the problems description $($not part $1$ of the answers$).$ That is$,$ write out how the LCS length can be expressed in terms of smaller instances of the problem. $3.$ Think about how to convert this into a dynamic program. What size table would you need for the LCS problem? $4.$ Interpret each table entry. That is$,$ give your explanation for what each entry