1. Using suffix trees, give an algorithm to find a longest common substring shared among three input strings: s₁ of length n₁, s₂ of length n₂ and s₃ of length n₃.

2. A non-empty string α is called a minimal unique substring of s if and only if it satisfies:

(i) α occurs exactly once in s (uniqueness),

(ii) all proper prefixes of α occur at least twice in s (mimimality), and

(iii) α >= l for some constant l.Give an optimal algorithm to enumerate all minimal unique substrings of s.

3. Redundant sequence identification: Given a set of k DNA sequences, S = {s₁, s₂........s_k }, give an optimal algorithm to identify all sequences that are completely contained in (i.e., substrings of) at least one other sequence in S.

4. Let S = {s₁, s_2,......,s_k} denote a set of k genomes. The problem of  fingerprinting is the task of identifying a shortest possible substring α_i from each string s_i such  that α_i is unique to s_i  i.e., no other genome in the set S has α_i. Such an α_i will be called a fingerprint of s_i. (Note that it is OK for α_i to be present more than once within s_i.) Give an algorithm to enumerate a fingerprint for each input genome, if one exists. Assume that no two input genomes are identical.

5. A string s is said to be periodic with a period α , if s is α^k for some k>=2. (Note that α^k is the string formed by concatenating α k times.) A DNA sequence s is called a tandem repeat if it is periodic. Given a DNA sequence s, determine if it is periodic, and if so, the values for α and k. Note that there could be more than one period for a periodic string. In such a case, you need to report the shortest period.

6. A non-empty string β is called a repeat prefix of a string s if ββ is a prefix of s. Give a linear time algorithm to find the longest repeat prefix of s.

7. Given strings s₁ and s₂ of lengths m and n respectively, a minimum cover of s₁ by s₂ is a decomposition s₁ = w₁w₂......w_k, where each w_i is a non-empty substring of s₂ and k is minimized. Eg., given s₁ = accgtatct and s₂ = cgtactcatc, there are several covers of s₁ by s₂ possible, two of which are: (i) cover₁: s₁ = w₁w₂w₃w₄ (where w₁ = ac, w₂ = cgt, w₃ = atc, w₄ = t) , and (ii) cover₂: s₁ = w₁w₂w₃w₄w₅ (where w₁ = ac, w₂ = c, w₃ = gt, w₄ = atc, w₅ = t). However, only cover₁ is a minimal cover. Give an algorithm to compute a minimum cover (if one exists) in O(m + n) time and space. If a minimum cover does not exist your algorithm should state so and terminate within the same time and space bounds. Give a brief justification of why you think your algorithm is correct | meaning, how it guarantees finding the minimial cover (if one exists).