This set of questions serves also as assignment 4, and is due at the beginning of class, 2:30pm, April 1, 1999. Be as succinct as possible. This assignment is an individual effort, and no outside help (web, friends, students, professors) is allowed. Hand your answers back the old-fashioned way, on paper.
| 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. |
| 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). |
| 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?) |
Copyright © 1999 Luc Devroye. Email: luc@cs.mcgill.ca.