Assignment 1 Question 1 This question is on the linear algorithm for building suffix tree (lecture 2). Give an example for a string…

Assignment 1 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)