Draw the decision tree for the deterministic version of Quicksort on an array with n = 3 elements.

Problem 2

Given an array A of n integers in the range [0,k), we would like to build an index, which we would like to use to answer any query of type what is the number of integers in A that are in the range [a,b]? For this purpose, write the following two procedures:

• Procedure PreProcess(A) should process A to build an index in O(n + k) time. The size of your index should be O(k).
• Procedure Query(A, a, b) should return the number of integers in A that are in the range [a,b] in O(1) time.

Problem 3

Let A be an m n matrix. The transpose of A is an n m matrix A⁰ such that for all 0 i < n and 0 j < m, A⁰(i,j) = A(j,i). For example, if

(1)

then

0 0 3

A0 = 9 0 8 (2)

0 1 0

1 0 0

Let k denote the number of non-zero entries in mn matrix A (in the above example, k = 5). We say that a matrix A is sparse if k = o(mn). Clearly, it is more efficient to store a sparse matrix using a special data structure, instead of storing it as a 2-dimensional array. One common data structure is known as the compressed sparse-row (CSR) representation.

In CSR representation, matrix A is stored using three arrays: R, C, and V . These arrays are respectively of length m + 1, k, and k. The array C stores the column indices of the non-zeros, such that for each 0 i m1, the subarray C[R[i]..R[i+1]1] stores the column indices of the ith row of A, in increasing order (for convenience, the indexing of the arrays starts from 0). For each C[j], V [j] stores the value of the corresponding non-zero entry, i.e., if R[i] j < R[i+1], then V [j] = A(i,C[j]). For example, the CSR representation of matrix A in Equation (1) is as follows:

R = < 0,2,3,5 >

C = < 1,3,2,0,1 > (3)

V = < 9,1,1,3,8 >

For this problem, you are asked to write the algorithm for transposing a matrix in CSR representation. In other words, write the pseudo-code of procedure Sparse-Transpose(R,C,V,m,n,k) that will return arrays R⁰, C⁰, and V ⁰, representing the transpose of the matrix represented by R, C, and V in row major format. For example, if your procedure is called with the R, C, and V in Equation (3), it should return:

R⁰ = < 0,1,3,4,5 >

C⁰ = < 2,0,2,1,0 > (4)

V ⁰ = < 3,9,8,1,1 >

which is the row-major representation of A⁰ in Equation (2). Your algorithm should work in O(m + n + k) time. (Hint: The algorithm can be thought of as a generalization of CountingSort).