CS 261, Spring 2013, Homework 7, Due Thursday, May 30 1. The standard deviation of a collection of n data values x_i may be calculated by the formula n sum(x_i^2) - (sum x_i)^2 s = sqrt( -------------------------- ). n (n-1) (a) Give an example that shows that the standard deviation is not decomposable. (b) Describe a decomposable range querying problem such that the standard deviation of the data values within a query range can be computed in constant time from the answer to your query. (We went through a similar example for the average in the lecture.) 2. In class we saw how to compute the average of any contiguous subarray of a one-dimensional matrix by looking up two sums of prefixes of the matrix. Suppose that we have a two-dimensional matrix A (such as the pixels in a grayscale image), and we store another matrix B of the same dimensions, such that the value in B[i,j] is the sum of all entries A[x,y] with 0 <= x <= i and 0 <= y <= j. Give a formula that uses the values in B to compute the average of any rectangular subarray of A in constant time. 3. Recall that in the dynamic prefix sum problem, we are maintaining an array of data values, subject to operations that update a single cell in the array or that query the sum of a prefix of the array. There is a solution that takes time O(log n) per operation and there is a lower bound showing that the problem cannot be solved more quickly than O(log n) per operation (in the cell probe model measuring the amount of communication between main memory and CPU needed to solve the problem) Now suppose that we are given a sequence of n operations in a batch, rather than individual operations one at a time. Does the lower bound imply that solving this batched problem requires Omega(n log n) time, in the same cell probe model? Why or why not?