CompSci 163/265, Spring 2016, Homework 6

  1. In the stable marriage algorithm described in class, the men propose to the women in preference order, and each woman accepts the best proposal she has seen so far. If there are $n$ men and $n$ women, how many women (as a function of $n$) can be forced to settle for their last choice? Describe a scenario that would cause this many women to be matched with last-choice men: what preference orderings cause this behavior, and what does the algorithm do when given this input?

  2. Let $N$ be an even number, and form an undirected graph with $n$ vertices numbered from $0$ to $n−1$ by adding edges connecting each vertex numbered $i$ to the three vertices numbered $i−1$, $i+1$, and $i+n/2\pmod{n}$. For instance, when $n$ is four, this graph can be drawn using the sides and diagonals of a square. For which values of $n$ is this graph bipartite? Explain how to find a $2$-coloring of the graph for the values of $n$ that make this graph bipartite, and how to find an odd-length cycle for the values of $n$ that make this graph non-bipartite.

  3. Recall that the Hopcroft–Karp algorithm finds a maximum matching in a bipartite graph by finding a sequence of alternating paths, where each path is chosen to be as short as possible. For instance, whenever it can, it will find a one-edge path connecting two unmatched vertices. For the graph of the cube (8 vertices and 12 edges) find a sequence of paths that this algorithm could find, such that at least one of your paths has more than one edge.

  4. (163 students:) Draw a 10-sided polygon (with axis-parallel sides and no holes) that can be partitioned into three rectangles in at least three different ways.

    (265 students:) Suppose that you are given an $n$-sided polygon with axis-parallel sides, to be partitioned into a minimum number $r$ of rectangles. Your polygon may have holes but the sides of the holes count towards $n$. What is the smallest value (best case) that $r$ might be, as a function of $n$? What is the largest value (worst case) that $r$ might be, as a function of $n$?