Notes:

• Algorithms should be given in pseudocode. Please try to avoid relying on features of particular programming languages that would be unfamiliar to readers unfamiliar with that programming language (for example, negative indices in Python or the Python itertools library).
• 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."
• Note that you can view source to see the LaTeX source for most of the formulas.

---

Problem : Complete the Canvas quiz on loop invariants and the Gale-Shapley algorithm.

Problem : Consider the following implementation of insertion sort.

insertionsort(A):
  i ← 1
  while i < len(A)
    insert(A, i)
    i ← i + 1

insert(A, i):
  j ← i
  while j > 0 and A[j-1] > A[j]
    temp ← A[j-1]
    A[j-1] ← A[j]
    A[j] ← temp
    j ← j - 1

• Write the pre- and post-conditions for the insert function as it is used in insertion sort above (what is the most insertionsort can guarantee to insert and what must insert guarantee to to insertionsort; be pedantic).
• The following is part of the invariant for the loop in insert:
  • $j = i - n$; and
  • $j$ is a valid index into $A$ no greater than $i$ ($0 \le j \le i$); and
  • $A[0], \ldots, A[i]$ is a permutation of $A_{in}[0], \ldots, A_{in}[i]$; and
  • no elements beyond index $i$ change (for all $k$ such that $i < k < len(A)$, $A[k] = A_{in}[k]$).
  Write the missing parts of the loop invariant.
• Prove that the insert function is correct with respect to its pre- and post-conditions using your loop invariant. You may skip the basis and induction steps for the four given parts of the invariant; do the basis and induction steps for your new parts and then do the termination and postcondition parts of the proof.

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 = 1$ or $i = 2$ so that row 1, for example, could store the ordering by speed and row 2 the ordering by accuracy); and
• a 1-D array type where type[i] gives either 1 or 2, corresponding to the preference list for machinist $i$.

For example, if the preference lists are

Machinist	$pm$	Welder	$pw$
$m_1$	$w_1, w_2, w_3, w_4$	$w_1$	$m_1, m_3, m_2, m_4$
$m_2$	$w_2, w_1, w_4, w_3$	$w_1$	$m_1, m_3, m_2, m_4$
$m_3$	$w_2, w_1, w_4, w_3$	$w_1$	$m_1, m_3, m_2, m_4$
$m_4$	$w_1, w_2, w_3, w_4$	$w_1$	$m_1, m_3, m_2, m_4$

Then n = 4, prefW = [1, 3, 2, 4], prefM = [ [1, 2, 3, 4], [2, 1, 4, 3] ], and type = [1, 2, 2, 1] (note that the arrays use 1-based indexing).

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