Recitation 4

Recitation notes for the week of September 17, 2025.

Homework reminders

Here are some gentle reminders about HW policies:

Make sure you submit your HW as a PDF only. Otherwise your submission will not be graded.
Remember to put collaborators and sources in your submission file. Use None if appropriate.
Can only collaborate with 2 other people and must be for both Q1 and Q2.
NO collaboration is allowed on Q3. Discussion about Q3 (outside of piazza) is not allowed.
We will be running MOSS to check for cheating on Q3.
Proof Idea and Proof Details must be clearly separated and labeled. Not doing so will result in a ZERO for the problem.

Question 1 on Homework 2

For this question, we are still using the Gale-Shapley algorithm (GS) and the stable marriage problem for matching couples, but we are adding a twist to it. One thing that the stable marriage problem does not do is handle divorces, as it assumes that the preferences do not change. What would happen if someone did change their preference list?

Problem Set-Up

$m_i$, $w_i$ $\in$ $M$, $W$ where $0 <i ≤n$
Each $m$, $w$ have preference lists $L_{m_i}$ or $L_{w_i}$ ranking the other group from most preferred to least preferred
The output of GS on this input is $S_{orig}$
After making $S_{orig}$, we change one preference list (gender doesn’t matter, but this example will change a female list) from $L_w$ to $L_w’$

Now after changing the preference list of one person, we run GS again. If it outputs a set $S_{new}$ that is disjoint with $S_{orig}$, then we call the person whose list changed a homewrecker.

Disjoint

Two sets are disjoint if they have no element in common. In this problem, the element is a pair $(m, w)$, so for the sets to be disjoint, then no pair $(m, w)$ can appear in both sets.

Part (a)

Problem Statement

Given that an instance of the stable marriage problem has a homewrecker, show that $S_{orig} \neq S_{new}$.

Proof Idea

Let's look at an example input.

Example 1

Women:

$w_1 : m_1 > m_2 > m_3$
$w_2 : m_1 > m_3 > m_2$
$w_3 : m_3 > m_2 > m_1$

Men:

$m_1 : w_1 > w_2 > w_3$
$m_2 : w_2 > w_3 > w_1$
$m_3 : w_3 > w_1 > w_2$

If we run GS on this example, with the following sequence and final stable matching:

$w_1$ proposes to $m_1$. He accepts.
$w_2$ proposes to $m_1$. He rejects since he prefers $w_1$ to $w_2$.
$w_2$ proposes to $m_3$. He accepts.
$w_3$ proposes to $m_3$. He accepts since he refers $w_3$ to $w_2$. $w_2$ is now free.
$w_2$ proposes to $m_2$. He accepts.

Since all women are now matched, the algorithm ends, producing the stable matching $S_{orig} = \{(m_1, w_1), (m_2, w_2), (m_3, w_3)\}$.

What would happen if we changed $m_3$’s preference list to:

$m_3 : w_2 > w_3 > w_1$

With this new change, running GS gives:

$w_1$ proposes to $m_1$. He accepts.
$w_2$ proposes to $m_1$. He rejects since he prefers $w_1$ to $w_2$.
$w_2$ proposes to $m_3$. He accepts.
$w_3$ proposes to $m_3$. He rejects since now he prefers $w_2$ to $w_3$. $w_3$ remains free.
$w_3$ proposes to $m_2$. He accepts.

Now GS produces $S_{new} = \{(m_1, w_1), (m_2, w_3), (m_3, w_2)\}$. This is not the same as $S_{orig}$.

Now we try and extend this to all $n$. Our family will be defined as follows:

For inputs where $n > 3$ (there are more than $3$ men and women), the preference lists are the same as the input above, with:

$w_4 > w_5 > ... > w_n$, and
$m_4 > m_5 > ... > m_n$

appended to each list.

For the remaining men and women, where $i>3$, the lists are:

$w_i : m_i > m_{i+1} > ... > m_n > m_1 > ... > m_{i-1}$
$m_i : w_i > w_{i+1} > ... > w_n > w_1 > ... > w_{i-1}$

With the original preference lists, the sequence of proposals is:

The first five proposals are exactly the same as in the first input above.
After the first 5 steps, $w_i$ proposes to $m_i$ for $i>3$ and $m_i$ accepts.

This produces $S_{orig} = \{(m_1, w_1), (m_2, w_2), …, (m_n, w_n)\}$

The change to the list of $m_3$ is as above, simply replacing the first three rankings as $w_2> w_3> w_1$ followed by $w_4 > w_5 > ... > w_n$.

Exercise

Argue that with this change $S_{new} = \{(m_1, w_1), (m_2, w_3), (m_3, w_2), (m_4, w_4), …, (m_n, w_n)\}$. Then argue why this is enough to prove part (a).

One thing to remember about GS when doing these problems and examples is that the sequence of proposals does not affect the output of the algorithm. Rather, the algorithm will only ever output one specific stable matching for a given input. For a proof of this property, read about Gale-Shapley in your textbook $:)$.

Part (b)

Problem Statement

Given that an instance of the stable marriage problem has a homewrecker, show that $S_{orig}$ and $S_{new}$ are disjoint.

Now we want to show a family that still upholds $S_{orig} \ne S_{new}$, but also take it a step further, and show that $S_{orig}$ and $S_{new}$ are disjoint (no person is paired to the same person in both sets). Remember, a stable matching is a set of pairs, not the pair itself.

Looking at the previous example, we see that that specific instance does not satisfy this ($(m_1, w_1)$ appears in both $S_{orig}$ and $S_{new}$).

Question 2 on Homework 2

Problem Statement

Eureka! You’ve done it. A Wanda Sykes cloning device. Wanda Sykes is the hottest name in comedy right now, so you quickly produce $n$ Wanda Sykes clones (each with their own original movie idea) and schedule them to meet with $n$ movie production companies across $m$ time slots for some $m\gt n$.

The schedule has the following properties:

Each Wanda Sykes clone meets with each production company exactly once.
No two Wanda Sykes clones meet the same production company in the same time slot.
No two production companies meet the same Wanda Sykes clone in the same time slot.

Days before the first meeting, someone in the industry gives you a tip: the production companies are desperate to produce a Wanda Sykes movie, but they only have the budget to afford one movie deal each. The only thing that could dissuade a company from doing business with Wanda Sykes is if one of the Wanda Sykes clones misses or cancels a meeting, and that company has yet to secure a movie deal.

It is customary to go out for celebratory drinks after making a deal in showbiz, so each Wanda Syke clone will have to clear their remaining schedule after they agree to a deal. And you can expect each production company to do the same.

In other words, the goal for each Wanda Sykes clone $S$ and the production company $P$ that she gets assigned to, is to truncate both of their schedules after their meeting and cancel all subsequent meetings in a way that doesn’t offend the other movie companies. A movie company is offended if $P$ plans to meet with $S$ on its truncated schedule and $S$ is already out for drinks with an agent representing some other production company $P'$.

Part (a)

Your first instinct is most likely to design a greedy algorithm (an algorithm that makes decisions without needing the entire input, so in this case, using just Wanda Sykes clone schedules, or just production company schedules) to solve the problem quickly. The problem with this is that these greedy algorithms either violate or outright ignore one of the stated properties or rules for this problem.

Here are two examples:

Algorithm Idea

What if we matched each Wanda Sykes clone to the last production company they were scheduled to meet with, such that the Wanda Sykes clone's schedule is truncated at their last meeting, essentially removing the remaining empty slots in their schedule?

Algorithm Details

        //input: n is the number of Wanda Sykes clones and production companies
        //input: m is the number of time slots
        //input: Wanda Sykes clone schedules are S[i] where 0 < i ≤ n and is of length m
        //input: Production company schedules are P[i] where 0 < i ≤ n and is of length m
        //input: each entry of the arrays will be 0 if the slot is free, or will 
        //       contain a number corresponding to a scheduledproduction company or  Wanda Sykes clone
        //return will be a list of pairs of production companies and Wanda Sykes clones
        
        ret = []
        
        for i from 1 to n:
            for j from m-1 to 0:
                if S[i][j] != 0:
                    ret.append((i,S[i][j]))
                    break
        
        return ret

(Dis)Proof by Counter-example

The issue here is each production company is not guaranteed to be matched to a unique Wanda Sykes clone. Consider the example in HW 2:

Production Company	Slot 1	Slot 2	Slot 3	Slot 4
$P_1$	$S_1$	free	$S_2$	free
$P_2$	free	$S_1$	free	$S_2$

Here we see that both Wanda Sykes clones have $P_2$ as their last meeting of the day, but this would mean $P_2$ is matched with $2$ Wanda Sykes clones, which is not allowed.

The main issue here is we are only considering the Wanda Sykes clones' schedules, and not paying any regard to how those schedules work with the schedules of the production companies.

Algorithm Idea

What if instead of scheduling the Wanda Sykes clones to their last production company, we matched each production companies with their last Wanda Sykes clone?

Algorithm Details

        //input: n is the number of Wanda Sykes clones and production companies
        //input: m is the number of time slots
        //input: Wanda Sykes clone schedules are S[i] where 0 < i ≤ n and is of length m
        //input: Production company schedules are P[i] where 0 < i ≤ n and is of length m
        //input: each entry of the arrays will be 0 if the slot is free, or will
        //       contain a number corresponding to a scheduledproduction company or  Wanda Sykes clone
        //return will be a list of pairs of production companies and Wanda Sykes clones
        
        ret = []
        
        for i from 1 to n:
            for j from m-1 to 0:
                if P[i][j] != 0:
                    ret.append((P[i][j],i))
                    break
        
        return ret

Exercise

Explain why the above greedy algorithm does not work.

Part (b)

Problem Statement

Now we want to find an algorithm that actually works for this problem. To do this, you should consider both the Wanda Sykes clone schedules and the production company schedules. Again, the end goal is to be able to match production companies to Wanda Sykes clones so the schedules of both can be truncated once they meet with their match.

Hint

As a hint, and to highlight what will be a recurring theme of this course, try and reduce this problem to one we have already seen in class. This will help reduce the original work you need to do, and will help you to see how a lot of the problems and algorithms in this course relate to each other.

Question 3 on Homework 2

Understanding the problem statement

Input to the problem

$m$ hospitals, each with a preference list of all $n$ students.

$n$ students, each with a preference list of all $m$ hospitals.

Difference from Stable Matching Problem in class

The number of hospitals and the number of students are different.
One hospital can have more than one open slot, but each student is only assigned to one hospital.
There are at least as many students as there are total number of available slots for all $m$ hospitals.

Overall Goal

Given $n$ hospitals and $m$ students, output one stable matching assignment of hospitals to students.

As in the Stable Matching problem, a stable assignment is one that does not have any instability. However, unlike the earlier case there can be two kinds of instability, which we talk about next.

Instability (kind 1)

There are students $s$ and $s'$, and a hospital $h$, so that:

$s$ is assigned to $h$, and
$s'$ is assigned to no hospital, and
$h$ prefers $s'$ to $s$.

For example, consider the following input: \[h_1 (2 \text{ spots}): s_1 > s_2 > s_3 > s_4~~~~ s_1: h_2 > h_1~~~~ s_3: h_1 > h_2\] \[h_2 (1 \text{ spot}):~ s_2 > s_4 > s_3 > s_1~~~~ s_2: h_2 > h_1~~~~ s_4: h_1 > h_2\] and the following assignment: \[\{(h_1, s_3), (h_1, s_4), (h_2, s_2)\}.\]

The above assignment is unstable because $s_1$ was not assigned to anyone, but is highest on $h_1$'s preference list.

Instability (kind 2)

There are students $s$ and $s'$, and hospitals $h$ and $h'$, so that:

$s$ is assigned to $h$ and
$s'$ is assigned to $h'$, and
$h$ prefers $s'$ to $s$, and
$s'$ prefers $h$ to $h'$.

For example, consider the following input: \[h_1 (2 \text{ spots}):~~~~ s_1 > s_2 > s_3 > s_4~~~~ s_1: h_2 > h_1~~~~ s_3: h_1 > h_2\] \[h_2 (1 \text{ spot}):~~~~~ s_2 > s_4 > s_3 > s_1~~~~ s_2: h_2 > h_1~~~~ s_4: h_1 > h_2\] and the following assignment: \[\{(h_1, s_1), (h_1, s_2), (h_2, s_4).\]

The above assignment is unstable because $h_2$ prefers $s_2$ to current ($s_4$) and $s_2$ prefers $h_2$ to current ($h_1$).

An example (input and output and why this is stable)

We will now go over the example given in HW 2.

Input:

                3                               <- Number of hospitals
                5                               <- Number of students
                1   2   3   5   1   4           <- Preference of the 1st hospital (most preferred first with first index is available slot)
                1   5   1   2   4   3           <- Preference of the 2nd hospital (most preferred first with first index is available slot)
                2   5   2   3   1   4           <- Preference of the 3rd hospital (most preferred first with first index is available slot)
                2   1   3                       <- Preference of the 1st student (most preferred first)
                3   2   1                       <- Preference of the 2nd student (most preferred first)
                3   1   2                       <- Preference of the 3rd student (most preferred first)
                1   2   3                       <- Preference of the 4th student (most preferred first)
                1   2   3                       <- Preference of the 5th student (most preferred first)

We claim that the following is a stable assignment:

                (1, 5)                          <- Pairing of the form (h,s)
                (2, 1)
                (3, 2)
                (3, 3)

Let’s take a look at why this output is stable:

$(1,5)$: Take a look at $\{2,3\}$ who rank higher in $h_1$'s preference list. If $2$ or $3$ prefer $1$ over their current partner or are unmatched, then there would be an instability.
$(2,1)$: $5$ is higher on $h_2$'s preference list. If $s_5$ is unmatched or prefers $h_2$ to their current partner, then there would be an instability.
Repeat for $(3,2)$ and $(3,3)$.

Asymptotic Notation

Overview of "linear" bounds on runtime

$O(n)$ - upper bound for worst case run time
- an upper bound, not the exact growth rate of the function
$\Omega(n)$ - lower bound for worst case run time (NOT THE BEST CASE RUNTIME)
- a lower bound, not the exact growth rate
$\Theta(n)$ - exact run time - if you can show something is $O(n)$ and $\Omega(n)$.

Simple example with search

The search problem

Given a string s, search for a character, c, in the string.

Consider the most basic way solve the above problem: i.e. iterate over list:

                        for a in s:
                            if (a == e):
                                return a
                            return -1

$O(n)$ worst case we will need to iterate over every element in the list. As our list grows, our worst case scenario grows linearly.

Another example

Calling the `len` function

Store the length in a function before even storing the string. For example if we store $s$ = cat, then len = $3$.

What are the asymptotic bounds on calling len?

Calling len will take the same amount of time no matter how big the string is, therefore it takes constant time:

$O(1)$ since worst case we find the length of the string in constant time.
$\Omega(1)$ since we cannot take less than constant time to find the length of the string.
Since big $O$ and big $\Omega$ are the same, this solution runs in $\Theta(1)$.

Common runtimes of algorithms

$O(n)$ - linear

Examples: computing the maximum in a list, merging two sorted lists.

$O(n^2)$ - quadratic

Arises naturally from two nested for loops, why?

Examples: brute force seeing two numbers in a list add up to another, brute force substring.

$O(\log n)$ - logarithmic

Example in class with binary search. Recap of why this is true:

                [1,2,3,4]     → takes 2 steps with a list of size 4
                [1,2][3,4]       
                [1][2][3][4]

                [1,2,3,4,5,6,7,8]    → takes 3 steps with a list of size 8 (double the size)
                [1,2,3,4][5,6,7,8]        
                [1,2][3,4][5,6][7,8]
                [1][2][3][4][5][6][7][8]

                [1,2,3,4,5] best case: searching for 3, worst case: searching for 5 
                [3,4,5]
                [4,5]
                [5]

So binary search is $O(\log n)$ and $\Omega(1)$ ($\Omega(\log{n})$ lower bound can also be showed-- left as an exercise!).

$O(n \log n)$

Common with any algorithm that splits the input into two and solves each piece recursively and combines the two pieces in linear time.

For example: Mergesort, so also common with any algorithm that sorts first then performs a linear operation on the input since $O(n \log n) + O(n) = O(n \log n)$.

Recitation 4

Homework reminders

Question 1 on Homework 2

Problem Set-Up

Disjoint

Part (a)

Problem Statement

Proof Idea

Example 1

Exercise

Part (b)

Problem Statement

Question 2 on Homework 2

Problem Statement

Part (a)

Algorithm Idea

Algorithm Details

(Dis)Proof by Counter-example

Algorithm Idea

Algorithm Details

Exercise

Part (b)

Problem Statement

Hint

Question 3 on Homework 2

Understanding the problem statement

Input to the problem

Difference from Stable Matching Problem in class

Overall Goal

Instability (kind 1)

Instability (kind 2)

An example (input and output and why this is stable)

Asymptotic Notation

Overview of "linear" bounds on runtime

Simple example with search

The search problem

Another example

Calling the len function

Common runtimes of algorithms

$O(n)$ - linear

$O(n^2)$ - quadratic

$O(\log n)$ - logarithmic

$O(n \log n)$

Further Reading

Calling the `len` function