Suppose you are given a $2^{n} \times 2^{n}$ checkerboard with one (arbitrarily chosen) square removed. Describe and analyze an algorithm to compute a tiling of the board by without gaps or overlaps by L- shaped tiles, each composed of 3 squares. Your input is the integer $n$ and two $n$-bit integers representing the row and column of the missing square. The output is a list of the positions and orientations of $\left(4^{n}-1 ight) / 3$ tiles. Your algorithm should run in $0\left(4^{n} ight)$ time. (Hint: First prove that such a tiling always exists. ] cs.vs. 1224