Algorithms  Assignment 4: Sorting in Linear Time

EECS 340/454: Algorithms 
Assignment 4: Sorting in Linear Time

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
A =


0 9 0 1
0 0 1 0
3 8 0 0

 (1)
then
A
0 =




0 0 3
9 0 8
0 1 0
1 0 0




(2)
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 >
V = < 9, 1, 1, 3, 8 >
(3)
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
, C
0
, 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 >
C
0 = < 2, 0, 2, 1, 0 >
V
0 = < 3, 9, 8, 1, 1 >
(4)
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).