EECS340-Assignment 4 Sorting in Linear Time Solved

Problem 1

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 A0 such that for all 0 ≤ i < n and 0 ≤ j < m, A0(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 m×n 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 ≤ m−1, 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 R0, C0, and V 0, 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:

                                                                             R0 =        < 0,1,3,4,5

                                                                              C0 =        < 2,0,2,1,0                                                   (4)

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

which is the row-major representation of A0 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).