You are given an n$\backslash$times n board with some squares marked. You are also given a bag of tiles. Each

tile can perfectly cover two adjacent squares on the board. Give an efficient algorithm $($using the

algorithms covered in class$)$ to determine if you can cover all marked squares with tiles without

overlapping any tiles or covering any non$-$marked squares. $($Hint: Think$$bipartite$).$You are given an $nn$ board with some squares marked. You are also given a bag of tiles. Each

tile can perfectly cover two adjacent squares on the board. Give an efficient algorithm $($using the

algorithms covered in class$)$ to determine if you can cover all marked squares with tiles without

overlapping any tiles or covering any non$-$marked squares. $($Hint: Think bipartite$).$