Problem 3 (25 pts] Greedy You are given two arrays ROW[1...) and COLUMN]1.m] of natural num- bers. ROW[i] counts the num

[answerhappygod]

Problem 3 25 Pts Greedy You Are Given Two Arrays Row 1 And Column 1 M Of Natural Num Bers Row I Counts The Num 1 (40.27 KiB) Viewed 60 times

Problem 3 (25 pts] Greedy You are given two arrays ROW[1...) and COLUMN]1.m] of natural num- bers. ROW counts the number of l's in the i-th row of a n x m binary matrix. Similarly, COLUMN[j] counts the number of l'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 0 0 [1 6 9). Summing all the elements across row 1 we get 1 +1+0+0 = 2. 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). 1 2 3 4 1|1|0|0 2 1010 2 COLUMN 2110 ROW (a) Show that the matrix decoding is not unique. (6) Design a greedy algorithm for reconstructing the matrix.