Data Structures - Assignment no. 10, May 31, 2006

Remarks:

• Please write your exercises in pen, or in clearly visible pencil. Please write very clearly.

• For every question where you are required to write pseudo-code, also explain your solution in words.

1. Show how to preprocess an array A of size n, such that the data structure supports the operation SUM(i, j). This operation computes A[i] + A[i + 1] + … + A[j − 1] + A[j]. The preprocessing time should be O(n), the space usage of the data structure should be O(n), and the query time should be O(1). \underline{Hint:} the solution is really simple! (once you find the trick). Think about a Prefix-Sum array – an array B where in location k the number written is A[1] + A[2] + … + A[k].

2. Give a solution to the Range Minima Problem with space usage O(n), preprocessing time O(n), and query-time O(log n). \underline{Reminder:} In the Range Minima Problem you need to preprocess an array A of size n, such that the data structure supports the operation RM(i, j). This operation computes MIN(A[i], A[i + 1], …, A[j]).

3. Let s be a string of length n and let T be its suffix tree.

(a) What is the maximum possible height of T as a function of n? (give the answer up to a constant). Give an example, you don’t have to prove that it is optimal.

(b) What is the minimum possible height of T as a function of n? (give the answer up to a constant). Give an example, you don’t have to prove that it is optimal.

4. Given two strings s_{1}, s_{2}, both of length n, and given an integer k, show an algorithm that finds the longest string s that appears at least k times in s_{1} and at least k times in s_{2}. \underline{Hint:} First think of how to find all of the longest strings that appear in s_{1} at least k times.