\documentclass[10pt]{article}

\PassOptionsToPackage{numbers, sort&compress}{natbib}

%\usepackage{changepage}

\usepackage{amsmath, amssymb, amsthm}
\usepackage{algorithm}
\usepackage{mathtools}
%\usepackage{caption}
%\usepackage{subcaption}
\usepackage{float}
\usepackage{framed}
\usepackage[noend]{algpseudocode}
\usepackage{enumitem}
\usepackage{thmtools, thm-restate}

\usepackage[utf8]{inputenc} % allow utf-8 input
\usepackage[T1]{fontenc}    % use 8-bit T1 fonts
\usepackage[hidelinks]{hyperref}       % hyperlinks
\usepackage{url}            % simple URL typesetting
\usepackage{booktabs}       % professional-quality tables
\usepackage{amsfonts}       % blackboard math symbols
\usepackage{nicefrac}       % compact symbols for 1/2, etc.
\usepackage{microtype}      % microtypography
\usepackage{xcolor}         % colors
\usepackage{wrapfig}
\usepackage{tabularx}
\usepackage{makecell}

% Recommended, but optional, packages for figures and better typesetting:
\usepackage{graphicx}
\usepackage{subcaption}
\usepackage{multirow}
\usepackage{fancyhdr}

\usepackage[capitalize,noabbrev]{cleveref}

\pagestyle{fancy}
\lhead{COMSC 312}
\rhead{Spring 2026}


\theoremstyle{definition}
\newtheorem{problem}{Problem}
\newenvironment{solution}{\begin{proof}[Solution]}{\end{proof}}

\title{Homework 1: Stable Matching I}
\date{}

\begin{document}

\maketitle
\thispagestyle{fancy}

\noindent You may work in groups, but you must write solutions yourself. List your collaborators at the top of your submission. 
As the semester progresses, when you are asked to design an algorithm, you will need to provide: (a) either pseudocode or a precise English description of the algorithm, (b) an explanation of the intuition for the algorithm, (c) a proof of correctness, (d) the running time of your algorithm and (e) justification for your running time analysis.

\vspace{1em}

\noindent \textbf{Instructions for submission:} Submit your homework as a single PDF file to the course Gradescope page. Either scan your \emph{legible} handwritten solutions or type them up in \LaTeX. 

\begin{problem}
    For the following matchings and preferences, determine whether the matching is stable. If it is not stable, identify an unstable pair and how you found it. Justify your answer.

    \vspace{1em}

    \noindent (a)  Let $S = \{ a, b, c \}$ be a set of students and $I = \{ 1, 2, 3 \}$ be a set of internships. The preferences are as follows with the matching given in bold:
    \begin{equation*}
        \begin{bmatrix}
            a: & \mathbf{1} & 2 & 3 \\
            b: & 2 & 1 & \mathbf{3} \\
            c: & 1 & \mathbf{2} & 3 \\
        \end{bmatrix}
        \qquad
        \begin{bmatrix}
            1: & b & \mathbf{a} & c \\
            2: & a & b & \mathbf{c} \\
            3: & a & \mathbf{b} & c \\
        \end{bmatrix}
    \end{equation*}

    \vspace{1em}

    \noindent(b) Let $R = \{ a, b, c, d \}$ be a set of residents and $H = \{ 1, 2, 3, 4 \}$ be a set of hospitals. The preferences are as follows with the matching given in bold:
       \begin{equation*}
        \begin{bmatrix}
            a: & 3 & \mathbf{2} & 1 & 4 \\
            b: & 1 & 2 & \mathbf{3} & 4 \\
            c: & 3 & \mathbf{1} & 2 & 4 \\
            d: & \mathbf{4} & 1 & 3 & 2 \\
        \end{bmatrix}
        \qquad
        \begin{bmatrix}
            1: & d & b & \mathbf{c} & a \\
            2: & \mathbf{a} & c & b & d \\
            3: & \mathbf{b} & c & a & d \\
            4: & \mathbf{d} & a & b & c \\
        \end{bmatrix}
    \end{equation*}
\end{problem}

% Use this environment for your solutions.
% \begin{solution}
%     This is a sample solution.
% \end{solution}

\newpage
\begin{problem}
    \noindent (a) Using the Propose-and-Reject algorithm, find two distinct stable matchings for the following preferences:
      \begin{equation*}
        \begin{bmatrix}
            a: & 3 & 4 & 2 & 1 \\
            b: & 2 & 3 & 4 & 1 \\
            c: & 4 & 1 & 2 & 3 \\
            d: & 4 & 3 & 1 & 2 \\
        \end{bmatrix}
        \qquad
        \begin{bmatrix}
            1: & d & c & b & a \\
            2: & c & d & a & b \\
            3: & d & c & b & a \\
            4: & a & d & c & b \\
        \end{bmatrix}
    \end{equation*}

    \vspace{1em}
    \noindent (b) Explain how you found both matchings and how they differ.
\end{problem}


\end{document}
