Notes:
- For this class is is generally not necessary to validate input in your pseudocode: if a problem says the input will be in a certain form then write your pseudocode under the assumption that the input is in that form.
- "Find/devise/give an efficient algorithm" means "find an algorithm that is as efficient as possible, and you have to figure out for yourself whether your solution can be improved."
Problem : The stable roommate matching problem is the problem of, given an even number $n$ of students and a preference list for each student, finding a partition $M$ of the students into size-2 subsets so that there is no $\{s_1, s_2\} \not\in M$ so that $s_1$ prefers $s_2$ to who they are matched with in $M$ and $s_2$ prefers $s_1$ to who they are matched with in $M$.
For example, if the preference lists are
- 0: 3 1 2
- 1: 2 0 3
- 2: 0 1 3
- 3: 0 1 2
Give a worst-case $O(n^2)$ algorithm to determine if a roommate
matching is stable.
The input to your algorithm should be an array match so that
match[n] gives the index of the student who student $n$
is matched with, and a 2-D array pref
so that pref[i][j] gives the index of the student
that student number $i$ ranked $j$th (student $i$'s list will not contain $i$).
You may assume that $n$ is even and that
the match array gives a valid perfect
matching.
Explain clearly why your algorithm runs in worst case time $O(n^2)$.
Problem : East Rock Motors (ERM) and Automotive Group of West Rock (AGWR) are merging. Each previously had a stable matching of their respective machinists and welders. Prove that the merged matching is also stable in the case where each worker's relative preferences among workers from their original company remains the same and they prefer any worker from their original company to workers from the other company.
Formally, let $M = \{m_1, ..., m_n, m_{n+1}, ..., m_{n+k}\}$ and $W = \{w_1, ..., w_n, w_{n+1}, ..., w_{n+k}\}$ be the set of machinists and welders respectively, where workers indexed $1, ..., n$ originally worked for ERM and workers indexed $n+1, ..., n+k$ originally worked for AGWR. Let $pm_i$ be machinist $i$'s original pre-merger preference list, which is a permutation of $w_1, ..., w_n$ if $1 \le i \le n$ and a permutation of $w_{n+1}, ..., w_{n+k}$ otherwise, and similarly for the welders' preference lists $pw_i$. Let $M_1$ be a stable matching of ERM workers and $M_2$ be a stable matching of AGWR workers, both with respect to the $pm_i$ and $pw_i$.
Suppose that we update the preference lists to contain workers from both merged companies: for each $i$, $pm'_i$ is $pm_i$ followed by some permutation of $w_{n+1}, ..., w_{n+k}$ if $1 \le i \le n$ and followed by some permutation of $w_1, ..., w_n$ if $n+1 \le i \le n+k$; the appended permutations may be different for each machinist. Let the welders' merged preferences $pw'_i$ be similar.
For example,
| Machinist | $pm$ | $pm'$ | Welder | $pw$ | $pw'$ |
|---|---|---|---|---|---|
| $m_1$ | $w_1, w_2, w_3$ | $w_1, w_2, w_3, w_4, w_5$ | $w_1$ | $m_1, m_3, m_2$ | $m_1, m_3, m_2, m_4, m_5$ |
| $m_2$ | $w_3, w_1, w_2$ | $w_3, w_1, w_2, w_4, w_5$ | $w_2$ | $m_2, m_1, m_3$ | $m_2, m_1, m_3, m_5, m_4$ |
| $m_3$ | $w_3, w_2, w_1$ | $w_3, w_2, w_1, w_5, w_4$ | $w_3$ | $m_2, m_3, m_1$ | $m_2, m_3, m_1, m_4, m_5$ |
| $m_4$ | $w_4, w_5$ | $w_4, w_5, w_1, w_2, w_3$ | $w_4$ | $m_5, m_4$ | $m_5, m_4, m_3, m_1, m_2$ |
| $m_5$ | $w_4, w_5$ | $w_4, w_5, w_3, w_1, w_2$ | $w_5$ | $m_4, m_5$ | $m_4, m_5, m_1, m_3, m_2$ |
Prove that $M_1 \cup M_2$ is stable with respect to the merged preference lists $pm'_i$ and $pw'_i$.
Problem : Show that there can be a single stable matching for an input of size $n$. That is, show how, for any $n$, to construct an input of size $n$ (the ordered list of preferences for each of the $n$ machinists and each of the $n$ welders) so that there is a unique stable matching for that input. You need not show that your resulting inputs have a unique stable matching; just show what your input is and what the unique stable matching is.
Problem : Show that there can be an exponential number of stable matchings for an input of size $n$. That is, find show that there is a real number $c > 1$ so that you can find an input with $\Omega(c^n)$ stable matchings. Explain your answer; this should include at least a recurrence and may also include an informal analysis of the recurrence using the substitution/iteration method.