please answer this questions: 1-Maximum square submatrix Given an m × n boolean
ID: 3826193 • Letter: P
Question
please answer this questions:
1-Maximum square submatrix Given an m × n boolean matrix B, find its
largest square submatrix whose elements are all zeros. Design a dynamic
programming algorithm and indicate its time efficiency. (The algorithm may
be useful for, say, finding the largest free square area on a computer screen
or for selecting a construction site.)
2-. a. Show that the time efficiency of solving the coin-row problem by straightforward
application of recurrence (8.3) is exponential.
b. Show that the time efficiency of solving the coin-row problem by exhaustive
search is at least exponential
Explanation / Answer
1) build a sum matrix S[R][C] for the known M[R][C].
a) reproduction first row and first columns as it is on or after M[][] to S[][]
b) For other entries, use following expressions to construct S[][]
If M[i][j] is 0 then
S[i][j] = min(S[i][j-1], S[i-1][j], S[i-1][j-1]) + 1
Else /*If M[i][j] is 1*/
S[i][j] = 1
2) Find the most entry in S[R][C]
3) by the value and coordinates of greatest admission in S[i], print
Sub matrix of M[][]
Time Complexity: O(m*n) where m is amount of rows and n is amount of columns in the known matrix.
Auxiliary Space: O(m*n) where m is amount of rows and n is amount of columns in the known matrix.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.