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.
  2. You are given a 2n x 2n 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.