Answers for fourth set of practice questions--CS251--Winter 1999


Question 1 Augmented data structures. Exercise 15.3.4 of Cormen, Leiserson and Rivest: Given an interval tree T and an interval i, describe how all intervals in T that overlap i can be listed in O(min (n, (k+1) log n)) time, where k is the number of intervals in the output list. Hint: You may need to modify the tree as you go along.
Answer We employ the interval tree of CLR, chapter 15. Copy tree T to T'. Consider a preorder traversal of T': in time O(n), we may identify all overlapping intervals. On T we perform the following operation repeatedly: find an overlapping interval and delete it from T (all this in time O(log n)). Halt when no further overlapping interval can be found. If there are k overlapping intervals, then the running time is O((k+1) log n). Alternate log n steps of the preorder algorithm and one step of the removal algorithm until one is finished. Every iteration takes log n time, and the total time is clearly O(min (n, (k+1) log n)) in the worst case. Note: there are other solutions as well. For example, one may recursively enter all subtrees where there is possible overlap. However, it is a bit harder to show that this algorithm takes time O((k+1) log n).
Question 2 Augmented data structures. A list of n different numbers is given. We call a pair (i,j) an inversion if i < j, but key[i] > key[j]. Thus, an increasing sequence has no inversions. A decreasing list has the maximum number of inversions, n(n-1)/2. Let K be the (unknown) number of inversions in the sequence. By creating an appropriate augmented data structure, give an algorithm for computing K that runs in time O(n log n).
Answer We use an order statistic tree according to the attribute key[.]. Store with each node the original index in the sequence, an integer between 1 and n which we shall call index[.]. Let size[x] be the size of the subtree rooted at node x. Let left[.] and right[.] be the child pointers. The creation of the tree takes time O(n log n). We also maintain an array treepoint[.], with treepoint[i] pointing to the node x in the tree having index[x]=i. (Thus, the i-th element in the sequence is key[treepoint[i]]. And index[treepoint[i]]=i of course.) Now, we run an algorithm as follows:
    inversions = 0
    for i=1 to n do
      r <= rank of treenode[i] (takes log n time)
      inversions += r-1
        (counts all inversions in which i < j,
        yet key[treepoint[i]]>key[treepoint[j]])
      delete node treepoint[i]
    output inversions
By deleting the points, the index i is at all times the smallest in the tree. Note that each step in each iteration takes time O(log n). Note: there is a solution in which the original sequence gets subjected to a mergesort, and the inversions are counted on-line as sorted lists as merged.
Question 3 Algorithms. We have to sort n different integers taking values between 1 and n^7. In a RAM model of computation (manipulating any integer in the given range takes one time unit), show how you can do this in O(n) time and O(n) space in the worst case. (Afterthought: if this is true, would this not be a fantastic sorting method?)
Answer Let x be an integer in the given range. Note that written in base n, x-1 has 7 digits (x-1 = x_0 + n x_1 + n^2 x_2 + ... + n^6 x_6), with each digit between 0 and n-1. In O(n) time, we can get all the coefficients for all n numbers (recall that we have a RAM model). Now, place the numbers in n piles according to x_0 - values, and place the piles on top of each other. This can be achieved by a simple chained linked list structure requiring O(n) space. The time is O(n). Note that the numbers are now sorted by last digit, large on top. Repeat this operation for x_1. After this round, the numbersare sorted by the last two digits. After seven rounds, the numbers are totally sorted. The overall time is O(n). Note: this is a special case of radix sort, section 9.3 of CLR.

Copyright © 1999 Luc Devroye. Email: luc@cs.mcgill.ca.