Homework 2, Advanced Data Structures

Due in class Monday, October 24th. Because this assignment is so difficult, you can work in groups.

  1. A useful additional operation in Link/Cut trees is Evert(v). This operation takes a node v, and makes it into the root of its tree. It does this by reversing the path from v to the root of its Link/Cut tree. Show how to modify the construction of Link/Cut trees presented in class to implement this. The running times of all operations, including Evert() should remain O(log n) amortized.

  2. The recurrence for the running time of the algorithm for computing a suffix array presented in class is T(n) = T(2n/3) + O(n). Show how to modify the algorithm to give one whose recurrence is T(n) = T(3n/7) + O(n). Extra credit: Is 3/7 the best possible?
    Or can you do better?

  3. For a string S, suppose you are given the suffix array SA of S, and the longest common prefix array (LCP) of S, and a range-min query data structure for the LCP. Given these three data structures (and S), you want to efficiently answer queries of the form: Given a pattern P find the number of occurrences of P in S.

    Part A: Give an algorithm that runs in time O(|P| log |S|).

    Part B: Give an algorithm that runs in time O(|P| + log |S|).

    Hint: You can use the LCP array along with the range-min structure to find the longest common prefix of any two suffixes in O(1) time.

Advanced Data Structures Home Page
Danny Sleator
Last modified: Tue Oct 11 12:35:24 2005