Cpt S 450 Homework #6 Please print your name! 1. LCS algorithm gives a way to decide how similar two given strings are.However, sometimes, we have to filter away some common subsequences thatare in some pattern. Here is a problem for you to solve. Given two strings aand /3, let 'Y to be a longest word satisfying all of the following conditions:• 'Y is a subsequence of a;• 'Y is a subsequence of /3;• 'Y does not contain abb.Design an algorithm that finds such a 'Y for any given a and /3. Also, analyze its complexity. 2. For any words a, /3, we use d(a, /3) to denote the length of an LCS(a, /3).Let L1 and L2 be two given regular languages. Design an algorithm thatcompute the number D with D = max d(a,/3).
o:EL1,/3EL2 (Warning: L1 and L2 could be infinite. Sometimes, D is infinite.) 3. Locality sensitive hash is a way to assign a number (called hash value) toan object so that when I try to find an object x from a set of objects thatis "similar" to a given object a, I only need to compute the hash value of aand compare with hash values of the objects in the set and find those objectswith almost the same hash value as a's. Is there any locality sensitive hashscheme for strings?