CS 163, Spring 2012, Homework 5, due Thursday, May 17

1. For the preferences listed below, find a solution to the stable marriage problem that, among all possible solutions, finds the most highly preferred partner for each woman.

   Men's preferences:
   Adam: Wanda, Xanthippe, Yasmin, Zelda
   Bob: Xanthippe, Wanda, Yasmin, Zelda
   Carl: Yasmin, Wanda, Xanthippe, Zelda
   Don: Zelda, Wanda, Xanthippe, Yasmin

   Women's preferences:
   Wanda: Bob, Adam, Carl, Don
   Xanthippe: Carl, Adam, Bob, Don
   Yasmin: Bob, Adam, Carl, Don
   Zelda: Carl, Adam, Don, Bob

2. Find a partition of the polygon shown below into the minimum possible number of rectangles.

   

3. Give an example of a graph that is not bipartite but that nevertheless satisfies the equation |M| + |I| = |V| where M is a maximum matching, I is a maximum independent set, and V is the set of all vertices. Show the maximum matching and maximum independent set for your example.

4. Find an alternating path starting at t and ending at u in the graph shown below.