$2.(\backslash (10+4\backslash )$ bonus pts$.)$ You are given an $\backslash ($ n $\backslash$times n $\backslash )$ binary matrix $\backslash ($ M $\backslash ),$ unlimited number of $\backslash ($ k $\backslash$times $1\backslash )$ column vectors and $\backslash (1\backslash$times k $\backslash )$ rows vectors for all $\backslash (1\backslash$leq k $\backslash$leq n $\backslash ).$ Each length $\backslash ($ k $\backslash )$ column$/$row vector can be used to cover continuous $\backslash ($ k $\backslash )$ elements of one column$/$row of $\backslash ($ M $\backslash ).$

$($a$)$ Devise a polynomial$-$time algorithm to compute the minimum number of vectors such that each $1$ is covered by at least one vector and that each $0$ is not covered by any vector. See an example below. Hint: transform this problem into a minimum vertex cover problem on a bipartite graph.

$($b$)$ Prove that your algorithm is correct.

CMPSC $465,$ Fall $2024,$ HW $8$

input: matrix M

output: $4$ vectors can cover all $1$ s $.$