Question 1

This question is on the linear algorithm for building suffix tree (lecture 2).

Give an example for a string S length n over final language, so that the last phase of the algorithm (expanding T n-1 to Tn) takes asymptotically as much time as possible.

Question 2

Describe efficient algorithm for the following problem

Input: a string S with length n over Σ = {1, 2, … , n}

Output: the shortest prefix T of S , so S is a prefix of T^n (concatenate T n times)

Example: for S = 12121 the output is T = 12

Question 3

Describe algorithm for the following problem with running time of O(|P| |T|):

Input: Strings P, T and a scoring function δ.

Output: a substring T’ of T so score(P, T’) is maximal, where as score(A, B) defined to be the alignment between A and B with maximum score according to the δ scoring function. (δ is a general scoring function)