\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}

\renewcommand{\O}{\mathcal{O}}

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


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

\title{Homework 2: Stable Matching II \& Algorithm Analysis 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}
    Gale and Shapley published their paper on the Stable Matching Problem in 1962, but a version of their algorithm had already been in use for ten years by the National Resident Matching Program, for the problem of assigning medical residents to hospitals.

    Basically, the situation was the following. There were $m$ hospitals, each with a certain number of available positions for hiring residents. There were $n$ medical students graduating in a given year, each interested in joining one of the hospitals. Each hospital had a ranking of the students in order of preference, and each student had a ranking of the hospitals in order of preference. We will assume that there were more students graduating than there were slots available in the $m$ hospitals. The interest, naturally, was in finding a way of assigning each student to at most one hospital, in such a way that all available positions in all hospitals were filled. (Since we are assuming a surplus of students, there would be some students who do not get assigned to any hospital.)

    In this case, there are two types of unstable pairs for matched and unmatched students.
    \begin{enumerate}
        \item Suppose student $s$ is not assigned to any hospital, and hospital $h$ prefers $s$ to at least one of the students it has been assigned. Then $(s, h)$ is an unstable pair.
        \item Suppose student $s$ is assigned to hospital $h'$, but prefers hospital $h$ to $h'$, and hospital $h$ prefers $s$ to at least one of the students it has been assigned. Then $(s, h)$ is an unstable pair.
    \end{enumerate}
    So we basically have the Stable Matching Problem, except that (i) hospitals generally want more than one resident, and (ii) there is a surplus of medical students.
    Show that there is always a stable assignment of students to hospitals, and give an algorithm to find one. Explain in words why your algorithm finds a stable matching.

    \vspace{5pt}
    \noindent \textbf{Hint:} think about how you might modify the Propose-and-Reject algorithm to handle this new setting.
\end{problem}

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

\begin{problem}
    Using the definition of Big-O notation, prove that $T(n) = 3n^2 + 5n + 10$ is $\O(n^2)$. Give the values of $c$ and $n_0$ that you choose in your proof.
\end{problem}

% \begin{solution}
%     This is a sample solution.
% \end{solution}

\begin{problem}
    Take the following list of functions and arrange them in ascending order of growth rate. That is, if function $g(n)$ immediately follows function $f(n)$ in your list, then it should be the case that $f(n)$ is $\O(g(n))$.
    \begin{align*}
        &n^{2.5} \\
        &\sqrt{2n} \\
        &n + 10 \\
        &n + 100 \\
        &10^n \\
        &n^2 \log n \\
        &2^{2^n} \\
    \end{align*}
    For each adjacent pair of functions in your list, give a brief justification for why the first function is $\O$ of the second function. Each justification should be precise but does not need to be a formal proof like in Problem 2. 

    \vspace{5pt}
    \noindent \textbf{Hint:} the correct ordering is not necessarily unique. For example, two items in the list may have the same growth rate, in which case they can be swapped without affecting the correctness of your ordering.
\end{problem}

% \begin{solution}
%     This is a sample solution.
% \end{solution}

\end{document}
