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.
-
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.
- Problem 1 in this
MIT problem set