The Problem

This problem is just to get you thinking about asymptotic analysis and input sizes.

An integer $n\ge 2$ is a prime, if the only divisors it has is $1$ and $n$. Consider the following algorithm to check if the given number $n$ is prime or not:

For every integer $2\le i\le \sqrt{n}$, check if $i$ divides $n$. If so declare $n$ to be not a prime. If no such $i$ exists, declare $n$ to be a prime.

What is the function $f(n)$ such that the algorithm above has running time $\Theta(f(n))$? Is this a polynomial running time-- justify your answer. (A tangential question: Why is the algorithm correct?)

The Problem

The stable marriage problem does not handle divorces. This is because we assume everyone is interested in everyone else of the opposite sex and we assume that the preferences do not change.

In this problem, we will see the effect of changes in preferences in the outcome of the Gale-Shapley algorithm. In this problem, assume that men propose to women (as done in the book and unlike what we did in the lecture) and consider the following scenario.

Given an instance of the stable marriage problem (i.e. set of women $W$ and the set of men $M$ along with their preference lists: $L_w$ and $L_m$ for every $w\in W$ and $m\in M$ respectively), call a woman $w\in W$ a reformer if the following property holds. There exists an $L'_w$ such that if $w$ changes her preference list to $L'_w$ (from $L_w$) then the Gale-Shapley algorithm matches everyone to someone else. In other words, let $S_{\textrm{orig}}$ be the stable marriage output by the Gale-Shapley algorithm for the original input and $S_{\mathrm{new}}$ be the stable marriage output by the Gale-Shapley algorithm for the new instance of the problem where $w$'s preference list is replaced by $L'_w$ (but everyone else has the same preference list as before). Then \[S_{\mathrm{orig}}\cap S_{\mathrm{new}}=\emptyset.\]

Here are the two parts:

• Part (a): You will first solve a simpler version of the problem. For every integer $n\ge 3$ argue the following: There exists an instance of the stable marriage problem with $n$ men and $n$ women such that there is a woman $w$ such that if she changes her preference list from $L_w$ to $L'_w$ then we have \[S_{\mathrm{orig}}\neq S_{\mathrm{new}}.\]
• Part (b): For every integer $n\ge 3$ argue the following: There exists an instance of the stable marriage problem with $n$ men and $n$ women such that there is a woman who is a reformer.

  Common Mistake

  A common mistake for this problem is to present an instance that solves part (a) but not part (b).

The Problem

The Big G company in the bay area decides it has not been doing enough to hire CSE grads from UB so it decides to do an exclusive recruitment drive for UB students. The Big G decides to fly over $n$ CSE majors from UB to the bay area during December for on-site interview on a single day. The company sets up $m$ slots in the day and arranges for $n$ Big G engineers to interview the $n$ UB CSE majors. (You can and should assume that $m>n$.) The fabulous scheduling algorithms at Big G's offices draw up a schedule for each of the $n$ majors so that the following conditions are satisfied:

• Each CSE major talks with every Big G engineer exactly once;
• No two CSE majors meet the same Big G engineer in the same time slot; and
• No two Big G engineers meet the same CSE major in the same time slot.

In between the schedule being fixed and the CSE majors being flown over, the Big G engineers were very impressed with the CVs of the CSE majors (including, ahem, their performance in CSE 331) and decide that Big G should hire all of the $n$ UB CSE majors. They decide as a group that it would make sense to assign each CSE major $S$ to a Big G engineer $E$ in such a way that after $S$ meets $E$ during their scheduled slot, all of $S$'s and $E$'s subsequent meetings are canceled. Given that this is December, the Big G engineers figure that taking the CSE majors out to the nice farmer market at the ferry building in San Francisco during a sunny December day would be a good way to entice the CSE majors to the bay area.

In other words, the goal for each engineer $E$ and the major $S$ who gets assigned to them, is to truncate both of their schedules after their meeting and cancel all subsequent meeting, so that no major gets stood-up. A major $S$ is stood-up if when $S$ arrives to meet with $E$ on their truncated schedule and $E$ has already left for the day with some other major $S'$.

Your goal in this problem is to design an algorithm that always finds a valid truncation of the original schedules so that no CSE major gets stood-up.

To help you get a grasp of the problem, consider the following example for $n=2$ and $m=4$. Let the majors be $S_1$ and $S_2$ and the Big G engineers be $E_1$ and $E_2$. Suppose $S_1$ and $S_2$'s original schedules are as follows:

CSE Major	Slot 1	Slot 2	Slot 3	Slot 4
$S_1$	$E_1$	free	$E_2$	free
$S_2$	free	$E_1$	free	$E_2$

In the above schedules "free" means that the student is not meeting any engineer.

In this case the (only) valid truncation is for $S_1$ to get assigned to $E_2$ in the third slot and for $S_2$ to get assigned to $E_1$ in the second slot. So the truncated schedule will look like this:

CSE Major	Slot 1	Slot 2	Slot 3	Slot 4
$S_1$	$E_1$	free	$E_2$ (truncate here)
$S_2$	free	$E_1$ (truncate here)

Here are the two parts:

• Part (a): In this part, we will see two algorithms that do not work. Your job will be, for each algorithm, to give an example input where the algorithm does not work (and briefly explain why that is the case).
  • Engineer-centric Algorithm: the first algorithm considers all engineers $E$ and say $E$'s last meeting is with CSE major $S$, then both $E$ and $S$'s schedules are truncated after their meeting.
  • CSE major-centric Algorithm: the second algorithm considers all CSE majors $S'$ and say $S'$s last meeting is with engineer $E'$, then both $E'$ and $S'$'s schedules are truncated after their meeting.
• Part (b): Design an efficient algorithm that always finds a valid truncation of the original schedules so that no CSE major gets stood-up.

  Hint

  In real life, you will almost never come across a problem whose description will match exactly with one you will see in this course. More often, you will come across problems that you have seen earlier but are stated in a way that don't look like the version you have seen earlier. One way to solve this problem would be to to simulate that situation. In algorithms-speak, you can to reduce the problem here to one that you have seen already.

  Common Mistake

  A common mistake for this part is to present an algorithm that does not take into account both the engineers' and CSE majors' schedules together.

The Problem

In this problem we will consider the extension of the stable matching problem that more closely resembles the resident matching program that NRMP administers.

We are given $m$ hospitals and $n$ medical students. Each hospital has a ranking of all the students in order of preference, and each student has a ranking of all the hospitals in order of preference. Unlike the stable matching problem, a hospital can have more than one open slots (but a student can be assigned at most one hospital). We will assume that there are more students than there are slots available in all the $m$ hospitals put together (they can be equal). The goal is to output a stable assignment of students to hospitals. Note that since there are more students than hospitals, some students may be not assigned to any hospital. Also no hospital is assigned more students than the number of openings it has.

An assignment of students to hospital is stable if neither of the following situation arises:

1. First type of instability: 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$.
2. Second type of instability: 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'$.

Input

The input is an instance of the national resident problem in a text file of the following format:

                m                                     <- Number of hospitals
                n                                     <- Number of students
                s01  s11  s21  s31 ...  sn1              <- Preference of the 1st hospital (most preferred first, s01 is number of available slots)
                s02  s12  s22  s32 ...  sn2              <- Preference of the 2nd hospital (most preferred first, s02 is number of available slots)
                s03  s13  s23  s33 ...  sn3              <- Preference of the 3rd hospital (most preferred first, s03 is number of available slots)
                s04  s14  s24  s34 ...  sn4              <- Preference of the 4th hospital (most preferred first, s04 is number of available slots)
                .
                .
                .
                s0m  s1m  s2m  s3m ...  snm              <- Preference of the mth hospital (most preferred first, s0m is number of available slots)
                h11  h21  h31 ...  hm1              <- Preference of the 1st student (most preferred first)
                h12  h22  h32 ...  hm2              <- Preference of the 2nd student (most preferred first)
                h13  h23  h33 ...  hm3              <- Preference of the 3rd student (most preferred first)
                h14  h24  h34 ...  hm4              <- Preference of the 4th student (most preferred first)

                .
                .
                .
                h1n  h2n  h3n ...  hmn              <- Preference of the nth student (most preferred first)
            

For example

                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)
                1   5   1   2   4   3           <- Preference of the 2nd hospital (most preferred first with first index is # available slot-- 1)
                2   5   2   3   1   4           <- Preference of the 3rd hospital (most preferred first with first index is # available slot-- 2)
                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)
            

Output

The output is an instance of stable matchings for the input in a text file of the following format:

                (h1, s1)             <- Pairing of the form (h,s)
                (h2, s2)             <- Pairing of the form (h,s)
                (h3, s3)             <- Pairing of the form (h,s)
                .
                .
                .
                (hn, sn)             <- Pairing of the form (h,s)
            

For example:

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

                                    ├── src
                                    │   ├── ub
                                    │       ├── cse
                                    │           ├── algo
                                    │               ├── Driver.java
                                    │               ├── HW2Utility.java
                                    │               ├── Match.java
                                    │               ├── PreferenceLists.java
                                    │               ├── Solution.java
                                    ├── testcases/
                                    │   ├── input1.txt
                                    │   ├── input2.txt
                                    │   ├── input5.txt
                                    ├── outputs/
                                    │   ├── output1.txt
                                    │   ├── output2.txt
                                    │   └── output5.txt

                                    /**
                                     * This method must be filled in by you. You may add other methods and subclasses as you see fit,
                                     * but they must remain within the HW2_Student_Solution class.
                                     * @return Your set of stable matches. Order does not matter.
                                     */
                                    public ArrayList<Match>> getMatches() {

                                      return new ArrayList<Match>>();
                                    }

                                    public class Match implements Comparable{
                                        public Integer student;
                                        public Integer hospital;

                                        Match(Integer student, Integer hospital) {
                                            this.student = student;
                                            this.hospital = hospital;
                                        }

                                        @Override
                                        public boolean equals(Object obj) {
                                            Match compare = (Match) obj;
                                            return (student.equals(compare.student)) && (hospital.equals(compare.hospital));
                                        }

                                        @Override
                                        public String toString() {
                                            return "(" + student + ", " + hospital + ")";
                                        }

                                        @Override
                                        public int compareTo(Match other) {
                                            return this.hospital.compareTo(other.hospital);
                                        }
                                    }

                                    ├── Driver.py
                                    ├── Utility.py
                                    ├── Match.py
                                    ├── PreferenceLists.py
                                    ├── Solution.py
                                    ├── testcases/
                                    │   ├── input1.txt
                                    │   ├── input2.txt
                                    │   ├── input5.txt
                                    ├── outputs/
                                    │   ├── output1.txt
                                    │   ├── output2.txt
                                    │   └── output5.txt

                                  class Solution:

                                      def __init__(self, m, n, hospital_list, student_list, hosp_open_slots):
                                          """
                                              The constructor exists only to initialize variables. You do not need to change it.
                                              :param m: The number of hospitals
                                              :param n: The number of students
                                              :param hospital_list: The preference list of hospitals, as a dictionary.
                                              :param student_list: The preference list of the students, as a dictionary.
                                              :param hosp_open_slots: Open slots of each hospital
                                              """
                                          self.m = m
                                          self.n = n
                                          self.hospital_list = hospital_list
                                          self.student_list = student_list
                                          self.hosp_open_slots = hosp_open_slots
                                        def get_matches(self):

                                          return []

                                

                                    ├── Driver.cpp
                                    ├── HW2Utility.h
                                    ├── Utility.h
                                    ├── PreferenceLists.h
                                    ├── Solution.cpp
                                    ├── testcases/
                                    │   ├── input1.txt
                                    │   ├── input2.txt
                                    │   ├── input5.txt
                                    ├── outputs/
                                    │   ├── output1.txt
                                    │   ├── output2.txt
                                    │   └── output5.txt

                                    Solution(int _m, int _n, map<int, vector<int>> _students, map<int, vector<int>> _hospitals) {
                                        m = _m;
                                        n = _n;
                                        students = _students;
                                        hospitals = _hospitals;
                                    }

                                    vector<pair<int,int>> getMatches() {
                                        stableMatchings.clear();

                                        return stableMatchings;
                                    }