You are given two arrays ROW[1..n] and COLUMN[1..m] of natural num- bers. ROW[i] counts the number...

Transcribed Image Text:

You are given two arrays ROW[1..n] and COLUMN[1..m] of natural num- bers. ROW[i] counts the number of 1's in the i-th row of a n x m binary matrix. Similarly, COLUMN [j] counts the number of 1's in the j-th row of the matrix. For example, ROW [2, 2] and COLUMN [2, 1, 1, 0] correspond to the 2x4 matrix 1 1 0 0 Summing all the elements across row 1 we get 1+1+0+0 = 2. 1 0 1 0 Similarly across row 2, we get 1 +0+1+0= 2. Thus, ROW is [2, 2]. If we sum the elements across the columns, we get 1 + 1 = 2, 1+0= 1, 0+ 1 = 1, and 0 + 0 =0. Therefore, COLUMN is [2, 1, 1, 0]. i 1 2 3 4 1 1 0 0 2 1010 2 COLUMN 2 110 ROW (a) Show that the matrix decoding is not unique. (b) Design a greedy algorithm for reconstructing the matrix. You are given two arrays ROW[1..n] and COLUMN[1..m] of natural num- bers. ROW[i] counts the number of 1's in the i-th row of a n x m binary matrix. Similarly, COLUMN [j] counts the number of 1's in the j-th row of the matrix. For example, ROW [2, 2] and COLUMN [2, 1, 1, 0] correspond to the 2x4 matrix 1 1 0 0 Summing all the elements across row 1 we get 1+1+0+0 = 2. 1 0 1 0 Similarly across row 2, we get 1 +0+1+0= 2. Thus, ROW is [2, 2]. If we sum the elements across the columns, we get 1 + 1 = 2, 1+0= 1, 0+ 1 = 1, and 0 + 0 =0. Therefore, COLUMN is [2, 1, 1, 0]. i 1 2 3 4 1 1 0 0 2 1010 2 COLUMN 2 110 ROW (a) Show that the matrix decoding is not unique. (b) Design a greedy algorithm for reconstructing the matrix.