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.