Practice Problem Set 7 (half-length) Solutions
Suppose that we wish to answer range median queries: that is, given a range [bottom,top] we wish to find the median of the keys within the range (the one in the middle position, rounding down if there are an even number of keys in the range). Describe how to do this using a constant number of ranking and unranking queries.
Solution:
unrank((rank(top)+rank(bottom))//2)Consider an algorithm for the dynamic prefix sum problem that merely stores the array \(A\) itself, changes one array cell in each update (without performing any read operations), and answers queries by reading and adding all of the array cells up to the given cell i. For the sequence of eight update and eight query operations given in the lecture notes as an example of a difficult-to-solve sequence, what is the information transfer for this algorithm at each node of the binary tree of operations? What is the total number of read operations that it performs?
Solution: The four queries in the right subtree of the root read left-subtree cells \(A[0]\), \(A[0]+A[2]+A[4]\), \(A[0]+A[2]\), and \(A[0]+A[2]+A[4]+A[6]\), respectively, for a total of ten words of information transfer; we similar get three words of information transfer at each child of the root and one word at each grandchild, for a total information transfer of 20 words. The actual number of read operations is \(1+5+3+7+2+6+4+8=36\). The number of reads is larger than the information transfer because the information transfer does not count words that are written and read in the same tree node, and it also does not count words that are initialized to zero and read before any update operation changes them.