Homework 8

The homework is due at class on Wednesday, November 5.

Practice problem (don't turn in):
  • [DPV] Problem 7.30 -- Hall's theorem. We didn't cover it in class
    but you should review it if you aren't familiar with it.

    1. We have a n x n grid. Some of the squares
      are occupied by pawns -- we are given a list of the
      k positions occupied by pawns. Can we place n rooks
      on the remaining squares (that is, squares unoccupied by pawns)
      so that each column contains exactly one rook and
      each row contains exactly one rook?

      For example,
      if n=3 and pawns are at positions (1,1),(1,2),(2,1),(2,2)
      then the answer is NO.
      Another example:
      if n=2 and pawns are at positions (1,1),(2,2)
      then the answer is YES (we can put the rooks at positions (1,2),(2,1).

      Give an efficient (running time polynomial in n) algorithm for this problem.

    2. Problem 1 in this MIT problem set