Homework 15
due Fri 3/15 in class

For the following problem, develop a divide-and-conquer algorithm to solve the problem using the 16 step divide-and-conquer algorithm development template. Give each of the steps; don't just give an algorithm — the point here is understanding the process and being able to apply it.

1. 

   Given a collection of L-shaped tiles and an n×n board with one square blacked out, find an arrangement of tiles that covers all but the blacked-out square. (Each L-shaped tile covers three board squares.) Tiles may not overlap each other. Assume n is a power of 2.