Sample problems for tutorial #5

1. Consider the problem of taking a sorted array A containing distinct (and not necessarily positive) integers, and determining whether or not there is a position i such that A[i] = i.

   • Describe a divide-and-conquer algorithm to solve this problem. Your algorithm should return such a position if it exists, or false otherwise. If A[i] = i for several different integers i, then you may return any one of them.
   • Analyze the running time of your algorithm as a function of the number of elements of A.
2. You are given a 2ⁿ x 2ⁿ grid in which a square has been removed, such as the grid on the left of the following figure:

   

   You want to cover this grid (but not the hole) with copies of the shape that is on the right in the figure (the one that consists of three squares stacked in an L-shape). For instance, the grid from the previous picture can be covered as follows:

   

   Notice that the L-shapes can be rotated. Design a divide and conquer algorithm to specify where to place the copies of the shape to cover the grid. Hint: you will need to place one copy before you can split the problem into subproblems.