Let A $$\backslash$epsilon$ $$\backslash \{0,1\backslash \}^\{$n $\backslash$times m$\}$$ be a matrix with n rows, m columns, and where every entry is either $0$ or $1.$ We will let $A$\_\{$ij$\}$$ denote the entry in ow i and column j$,$ so for example $A$\_\{11\}$$ is the top left entry, $A$\_\{$n$1\}$$ is the bottom$-$left entry, $A$\_\{1$m$\}$$ is the top$-$right entry, and $A$\_\{$nm$\}$$ is the bottom$-$right entry. Suppose that we want to find the largest integer k such that A contains a k $$\backslash$times$ k contiguous submatrix consisting of all $0\text{'}$s$.$ In other words, we want to find the largest k such there exists values i$,$ j such that $A$\_\{$xy$\}$$ $=0$ for all i$-$k $$<$$ x $$\backslash$leq$ i and j$-$k $$<$$ y $$\backslash$leq$ j$.\backslash \backslash$

We will design a dynamic programming algorithm that runs in O$($nm$)$ time for this problem.$\backslash \backslash$

$($a$)$ For every i$,$ j $$\backslash$epsilon$ $$\backslash$mathbb$\{$N$\}$$ with $1$ $$\backslash$leq$ i $$\backslash$leq$ n and $1$ $$\backslash$leq$ j $$\backslash$leq$ m$,$ let S$($i$,$ j$)$ denote the maximum value of k such that there is a k $$\backslash$times$ k contiguous submatrix of A consisting of all $0\text{'}$s whose bottom$-$right corner is at $($i$,$ j$)($row i$,$ column j$).$ Write a recursive formula for S$($i$,$ j$)$ and prove that the formula is correct.$\backslash \backslash$

$($b$)$ Give a dynamic programming algorithm based on your solution to part $($a$),$ and prove that it correctly finds the largest possible value of k and runs in time O$($nm$).\backslash \backslash$