Note: 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.

Problem : Give a worst-case $O(n^2)$ algorithm to determine if a matching is stable. The machinists will be labelled $1$ through $n$ and the welders will be numbered likewise. The input to your algorithm should be an array match so that match[n] gives the index of the welder machinist number $n$ is matched with, and two 2-D arrays prefM and prefW so that prefM[i][j] gives the index of the welder that machinist number $i$ ranked $j$th and similarly for prefW. You may assume that the match array gives a valid perfect matching. Explain clearly why your algorithm runs in worst case time $O(n^2)$.

Problem : Consider the special case of the stable matching problem with $n$ machinists and $n$ welders in which all the preferences are the same: each machinist's preference from highest to lowest are $w_1, w_2, \ldots, w_n$, and each welder's preferences are $m_1, m_2, \ldots, m_n$. Prove that in this special case there is a unique stable matching.

Problem : Describe a $\Theta(n)$ algorithm to find a stable matching in the following special case: every welder has the same preference list, and every machinist has one of two preference lists (so perhaps welders are ranked by either speed or accuracy and some machinists prefer fast welders while others prefer accurate welders). The inputs will be

• $n$, the number of machinists (equal to the number of welders),
• a 1-D array prefW where prefW[i] gives the index of the machinist ranked $i$th by all the welders;
• a 2-D array prefM where prefM[i][j] gives the index of the welder ranked $j$th according to machinist preference list $i$ ($i = 0$ or $i = 1$ so that row 0, for example, could store the ordering by speed and row 1 the ordering by accuracy); and
• a 1-D array type where type[i] gives either 0 or 1, corresponding to the preference list for machinist $i$.

You needn't prove that your algorithm is correct, but you should explain why your algorithm runs in $\Theta(n)$ time.

Problem : A squash match ("match" here used in the sense of a contest between two sides) between two teams each with $n$ players consists of $n$ individual matches between players from opposite teams so that each player plays in exactly one individual match. Before the match, the teams determine a sequence of players to play in the individual matches. Assuming that the $2n$ players can be ordered by skill (with no ties) and that a player of higher skill always beats a player of lower skill, is it always possible, no matter the skill order, to create the sequences so that neither team can increase the number of individual matches it will win by unilaterally changing its sequence (so the sequences are stable, in some sense)?

For example, if the players on team 1 are A, B, and C and the players on team 2 are X, Y, and Z, the skill order from most to least skilled is A, B, X, Y, Z, C, and team 1's sequence is A, B, C and team 2's is Z, X, Y then A beats Z, B beats X, and Y beats C, making 2 wins total for team 1, and this does not change if team 1 changes its sequence unilaterally or if team 2 changes its sequence unilaterally, so there are stable sequences for the given skill order.

Devise an efficient algorithm to find such stable sequences, explain its worst-case running time, and prove that it is correct, or give an example of a skill order so that there are no stable sequences and explain why there are no stable sequences.