[SOLVED] EECS340 Assignment 4- Sorting in Linear Time

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 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 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).