The best programs are written so that computing machines can perform them quickly and so that human beings can understand them clearly. A programmer is ideally an essayist who works with traditional aesthetic and literary forms as well as mathematical concepts, to communicate the way that an algorithm works and to convince a reader that the results will be correct. ― Donald E. Knuth

# Algorithms

## Miscellaneous

Problem :-
Given a matrix of 0s & 1s, find the maximum size square submatrix with all values as 1.
Consider the following matrix with 6 rows & 5 columns :-
0    1    0    0    1
1    0    0    1    0
0    1    1    1    1
0    1    1    1    0
1    1    1    1    1
0    0    0    0    0
Maximum size square sub-matrix is :-
1    1    1
1    1    1
1    1    1

Solution :-
Suppose the input matrix is mat [ m ][ n ]. We will maintain an auxilliary matrix aux [ m ][ n ] where each entry of aux is given by aux [ i ][ j ] = min ( aux [ i ][ j - 1 ] , aux [ i - 1 ][ j ] , aux [ i - 1 ][ j - 1 ] ) + 1 if mat [ i ][ j ] == 1 else aux [ i ][ j ] = 0 . Then we find the maximum entry in the aux matrix ( suppose it is k ) and backtrace from there to find the maximum square submatrix of size k by moving k cells upwards and leftwards.
See the implementation below.