% -*- compile-command: "rubber -d hw.1.tex" -*-
\documentclass[11pt]{tufte-handout}

\usepackage{times,graphicx,epstopdf,fancyhdr,amsfonts,amsthm,amsmath,algorithm,algorithmic,xspace,hyperref,qrcode}

%\textwidth 7in
%\textheight 9.5in


\pagestyle{fancy}

\lhead{CSCI 280: Algorithms -- Spring 2017}
\chead{}
\rhead{Brent Yorgey}
\lfoot{Homework 1}
\rfoot{Due: 4:00pm, Friday, January 27}
\cfoot{\thepage}
\renewcommand{\headrulewidth}{0.4pt}
\renewcommand{\headwidth}{\textwidth}
%\renewcommand{\footwidth}{\textwidth}
%\addtolength{\headwidth}{\marginparwidth}
%\addtolength{\headwidth}{\marginparsep}
\renewcommand{\footrulewidth}{0.4pt}

\newtheorem{claim}{Claim}
\newtheorem{definition}{Definition}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}{Lemma}
\newtheorem{observation}{Observation}
\newtheorem{question}{Question}

\begin{document}

This assignment has several questions that warrant proofs.  Try to
emulate the proof style that we have used in class and the proof style
that appears in the text.  That is, make sure your reasoning flows
logically from one statement to another.  You should edit your proofs
to make sure they read well.  Abstraction is crucial.  That is,
identify and isolate common ideas.  Write clearly and concisely or use
\LaTeX \ to typeset your solutions.

\marginnote{\qrcode{This\ is\ a\ hint.}}  On homework assignments
throughout the semester, hints will be provided in QR codes in the
margin, numbered by their corresponding question.  Some questions may
have multiple hints; generally the hints are in order of hintiness.
If you do not have a device capable of reading QR codes, you can find
the hints in the \verb|.tex| source for this document, linked from the
course webpage.

Start early. Ask for help if you need it.  Have fun!

\begin{question}
  Decide whether you think the following statements are true or false.
  If a statement is true, give a short explanation/proof.  If it's
  false, give a counterexample.
\begin{description}
\item [(a)] For every instance of the Stable Matching Problem, there
  is at least one stable matching containing a pair $(p,a)$ such that
  $p$ is ranked first on the preference list of $a$ and $a$ is ranked
  first on the preference list of $p$.

\item [(b)] Consider an instance of the Stable Matching Problem in
  which there exists a proposer $p$ and an accepter $a$ such that $p$
  is ranked first on the preference list of $a$ and $a$ is ranked
  first on the preference list of $p$.  Then the pair $(p,a)$ belongs
  to every possible stable matching for this instance.
\end{description}
\end{question}


\begin{question} \label{q:stable-roommate}
  Consider the following problem, called the {\em Stable Roommate
    Problem}.  There are $2n$ people, each of whom ranks the other
  $2n-1$ people in order of cohabitation preference.  For example,
  Alice, Bob, Carlos, and Don might have the following rankings:

\begin{table}[h]
\begin{center}
\begin{tabular}{r|ccc}
Name & \multicolumn{3}{c}{Preference}\\
\hline
Alice & Bob & Carlos & Don\\
Bob & Alice & Carlos & Don \\
Carlos & Don & Alice & Bob \\
Don & Carlos & Alice & Bob
\end{tabular}
\end{center}
\end{table}

\marginnote{\emph{\ref{q:stable-roommate}}\quad\qrcode{Note\ that\
    the\ Gale-Shapley\ algorithm\ is\ irrelevant,\ since\ it\ is\ for\
    solving\ a\ different\ problem.}}
The goal is to find a stable matching ({\em i.e.,} $n$ pairs of
roommates such that no two people prefer each other to their current
roommate).  We saw in class that a stable matching always exists for
instances of the stable matching problem.  Do stable matchings always
exist for the stable roommate problem?  If so, provide a proof.  If
not, give a counterexample.
\end{question}

\begin{question}[Algorithms in the wild] \label{q:wild} The National
  Residency Matching Program (NRMP) matches medical students with
  residency programs.  Here is what the NRMP says on their website:
\begin{quote}
  The NRMP Main Match provides an impartial venue for matching
  applicants' preferences for residency positions with program
  directors' preferences for applicants. Each year approximately
  16,000 U.S. allopathic medical school seniors and 15,000 graduates
  of osteopathic, Canadian or foreign medical schools compete for
  approximately 24,000 residency positions.
\end{quote}
In this matching problem, there are $n$ students and $m$ hospitals.
Each hospital $h_{i}$ has $p_{i}$ available positions.  Each student
ranks the $m$ hospitals and each hospital ranks the $n$ students.
Since there are more students than total positions available, we
assume that $n > \sum_{i=1}^{m} p_{i}$.  Thus, some students are never
matched.  As a result, we need a slightly expanded version of
stability.  As before, the matching is unstable if
\begin{itemize}
\item $s$ is assigned to $h$ and $s'$ is is assigned to $h'$ but $s$
  prefers $h'$ to $h$ and $h'$ prefers $s$ to $s'$.
\end{itemize}
But it is also unstable if
\begin{itemize}
\item $s$ is assigned to $h$ and $s'$ is not assigned to a hospital
  but $h$ prefers $s'$ to $s$.
\end{itemize}
\marginnote{\emph{\ref{q:wild}}\quad\qrcode{You\ can\ choose\ whether\
    hospitals\ or\ students\ are\ the\ proposers.\  One\ choice\ is\
    easier\ than\ the\ other.}}
Give an algorithm to find a stable matching of students to hospitals
where every hospital position is filled with a student.  Prove that
your algorithm is correct.
\end{question}

\begin{question}
  Implement your algorithm from Question~\ref{q:wild} in a programming
  language of your choice.  Your program should take two files {\tt
    sranks} and {\tt hranks} as input.  The file {\tt sranks} is a
  ranking of hospitals for each student.  The format of the file is
\begin{verbatim}
student_name1,hos_rank1,hos_rank2, ...,hos_rankm
student_name2,hos_rank1,hos_rank2, ...,hos_rankm
.
.
\end{verbatim}
  The file {\tt hranks} is a ranking of students for each hospital.
  The format of the file is
\begin{verbatim}
hospital_name1,numslots,stu_rank1, stu_rank2, ..., stu_rankn
hospital_name2,numslots,stu_rank1, stu_rank2, ..., stu_rankn
.
.
\end{verbatim}
  where {\tt numslots} is the number of available slots for that
  hospital.  The output should be a stable matching of students to
  hospitals.  The format of the output should be
\begin{verbatim}
hospital1,student1,student2,...
hospital2,student1,student2,...
.
.
\end{verbatim}
  where each hospital is assigned the appropriate number of students.
  Run your program on the {\tt sranks} and {\tt hranks} files linked
  on the course website. If you need help choosing a programming
  language or figuring out how to read and parse the input files,
  please come talk to me!

  Submit a \textbf{printout of your program}
  along with the rest of this assignment.  Submit the properly
  formatted output file \textbf{electronically via Moodle} (so that I
  can run automated tests to ensure your generated matching is
  stable).
\end{question}

\begin{question}
On a scale of 1 to 10, with 1 being ``my pet goldfish could do it in
its sleep'' and 10 being ``who do you think I am, Einstein?'', how
difficult was this assignment?  How many hours would you estimate that
you spent on it?
\end{question}

\end{document}
