\documentclass{homework}

\insolution{\author{Carl Eastlund (\url{cce@ccs.neu.edu})}}
\subject{CS 4800: Algorithms and Data}
\insolution{\date{\today}}
\inassignment{\date{Due \textbf{Thursday, October 4, 2012} at \textbf{9:00am}}}
\title{Homework 2}
\insolution{\subtitle{Sample Solution}}

\begin{document}

\maketitle

\inassignment{
  \paragraph{Group Formation:}
  This homework will be done in groups of 2-4.  Each group must send one email
  to \url{cce@ccs.neu.edu}, copied to all other group members, announcing the
  homework group by \textbf{Wednesday, September 26, 2012} at \textbf{9:00am}.
}

\inassignment{
  \paragraph{Submission Instructions:}
  This homework will be submitted online via email.  Send your submissions to
  \url{cce@ccs.neu.edu} in the following format:
  \begin{enumerate}
  \item The subject of the email must be ``\texttt{CS 4800 Homework 2
    Submission}''.
  \item The recipients of the email must include all members of the team.
  \item The homework solution must be included as an attachment.
    \begin{enumerate}
    \item The attachment must be in \texttt{.zip} or \texttt{.tar.gz} format.
    \item The attachment's name must be the team members' last names in
      alphabetical order, lower case, separated by hyphens, plus the appropriate
      extension.  For example, the team of Sam Raimi and John Doe would submit
      either \texttt{doe-raimi.zip} or \texttt{doe-raimi.tar.gz}.
    \item The attachment must contain a single top-level directory of the same
      name, minus extension.  This directory must contain the following:
      \begin{enumerate}
      \item Solutions to prose exercises must be included as
        \texttt{solution.pdf}.
      \item Solutions to programming exercises must be included as executable
        programs that run correctly on \url{login.ccs.neu.edu}; filenames
        are given in the exercises below.
      \item The source code for each exercise must be included.  The file
        \texttt{README.txt} must specify the name, subdirectory (if any), and
        language of each program's source code.
      \item Any other files may be included in support of the assignment
        (\emph{e.g.}, external programs or libraries necessary to run the
        executables), but their contents will be disregarded for purposes of
        grading.
      \end{enumerate}
    \end{enumerate}
  \end{enumerate}
}

\exercise[(10 points)]
\begin{problem}
  The Stable Matching Problem, as discussed in the text, assumes that all men
  and women have a fully ordered list of preferences.  In this problem we will
  consider a version of the problem in which men and women can be
  \emph{indifferent} between certain options.  As before we have a set \(M\) of
  \(n\) men and a set \(W\) of \(n\) women.  Assume each man and each woman
  ranks the members of the opposite gender, but now we allow ties in the
  ranking.  For example (with \(n=4\)), a woman could say that \(m_1\) is ranked
  in first place; second place is a tie between \(m_2\) and \(m_3\) (she has no
  preference between them); and \(m_4\) is in last place.  We will say that
  \(w\) \emph{prefers} \(m\) to \(m'\) if \(m\) is ranked higher than \(m'\) on
  her preference list (they are not tied).

  With indifferences in the rankings, there could be two natural notions for
  stability.  And for each, we can ask about the existence of stable matchings,
  as follows.
  \begin{enumerate}

  \item A \emph{strong instability} in a perfect matching \(S\) consists of a
    man \(m\) and woman \(w\), such that each of \(m\) and \(w\) prefers the
    other to their partner in \(S\).  Does there always exist a perfect matching
    with no strong instability?  Either give an example of a set of men and
    women with preference lists for which every perfect matching has a strong
    instability; or give an algorithm that is guaranteed to find a perfect
    matching with no strong instability \emph{and prove the guarantee}.

  \item A \emph{weak instability} in a perfect matching \(S\) consists of a man
    \(m\) and a woman \(w\) such that their partners in \(S\) are \(w'\) and
    \(m'\), respectively, and one of the following holds:
    \begin{itemize}
    \item \(m\) prefers \(w\) to \(w'\), and either \(w\) prefers \(m\) to
      \(m'\) or is indifferent; or
    \item \(w\) prefers \(m\) to \(m'\), and \(m\) either prefers \(w\) to
      \(w'\) or is indifferent.
    \end{itemize}
    In other words, the pairing between \(m\) and \(w\) is either preferred by
    both, or preferred by one while the other is indifferent.  Does there always
    exist a perfect matching with no weak instability?  Either give an example
    of a set of men and women with preference lists for which every perfect
    matching has a weak instability; or give an algorithm that is guaranteed to
    find a perfect matching with no weak instability \emph{and prove the
      guarantee}.

  \end{enumerate}
\end{problem}

\insolution{
  \begin{solution}
    \begin{enumerate}

    \item Yes, in the Stable Matching Problem with indifferences, there always
      exists a solution with no strong instability.  To find such a solution,
      first assign an arbitrary ordering to each indifference in the given
      preference lists.  For instance, if woman \(w\) is indifferent between
      \(m\) and \(m'\), we could arbitrarily choose the ordering that \(w\)
      prefers \(m\) to \(m'\).  Use the resulting indifference-free preferences
      and run the Gale-Shapley algorithm on the problem.  Any strong instability
      in the result with respect to the original preferences would have to
      correspond to an instability in the result of the Gale-Shapley algorithm.
      Since this is impossible, the solution from the Gale-Shapley algorithm
      must constitute a strong instability-free solution to the problem with
      indifferences.

    \item No.  Consider the case where \(m\) and \(m'\) both prefer \(w\) to
      \(w'\), and both \(w\) and \(w'\) are indifferent to \(m\) and \(m'\).
      The two possible perfect matchings are \((m,w);(m',w')\) and
      \((m,w');(m',w)\).  In the first case, \((m',w)\) constitutes a weak
      instability; in the second case, \((m,w)\) constitutes a weak
      instability.

    \end{enumerate}
  \end{solution}
}

\exercise[(10 points)]

\begin{problem}
  \label{problem:selection-sort}
  Consider sorting a sequence \(S\) of \(n\) numbers by first finding the
  smallest element and using it as the first element of the result.  Then find
  the second smallest element, and use it as the second element of the result.
  Continue in this manner for all \(n\) elements of \(S\).  This algorithm is
  known as \emph{selection sort}.
  \begin{enumerate}
  \item Implement selection sort for lists.  The executable file
    \texttt{selection-sort-list} must read a JSON sequence of integers from
    \texttt{stdin} and write the corresponding sorted JSON sequence of integers
    to \texttt{stdout}.
  \item \label{subproblem:selection-sort-list-impl} Give the best- and
    worst-case running times of selection sort for lists in \(\Theta\)-notation.
  \item Implement selection sort for arrays.  The executable file
    \texttt{selection-sort-array} must read a JSON sequence of integers from
    \texttt{stdin} and write the corresponding sorted JSON sequence of integers
    to \texttt{stdout}.  For full credit, the algorithm must be entirely
    \emph{in-place}: you may not allocate any extra arrays.

  \item Give the best- and worst-case running times of selection sort for
    arrays in \(\Theta\)-notation.
  \end{enumerate}
\end{problem}

\insolution{
  \begin{solution}
    \begin{enumerate}
    \item See code.
    \item \(\Theta(n^2)\) in both cases.  For each element \(i\) of the result,
      the algorithm must scan \(n-i\) elements of the list to determine the
      smallest, regardless of the order of inputs.  As
      \(\sum_{i=0}^{n}(n-i)=\frac{n(n+1)}{2}\), this requires quadratic time.
    \item See more code.
    \item \(\Theta(n^2)\) in both cases, for the same reasons as with lists.
    \end{enumerate}
  \end{solution}
}

\exercise[(10 points)]

\begin{problem}
  Consider an algorithm for sorting a prefix of a sequence.  To sort a prefix of
  \emph{at least} length \(n\), follow these steps:
  \begin{enumerate}

  \item \label{step:take} Find the longest forward- or backward-sorted prefix of
    the sequence.

  \item \label{step:reverse} Reverse the prefix if necessary.

  \item \label{step:check} If the sorted prefix's length \(k\) is at least
    \(n\), return the prefix.

  \item \label{step:recur} Otherwise, continue with the rest of the list.
    Recursively sort a prefix of the remainder, of at least length
    \(\lfloor\nicefrac{k}{2}\rfloor\).  (\emph{\textbf{Errata:}} the minimum
    length of the new prefix was previously given as \(k\).  Rounding down to
    half of \(k\) affects the complexity of the algorithm, though not its
    correctness.)

  \item \label{step:merge} Merge the old and new prefixes together.

  \item \label{step:repeat} Repeat from step~\ref{step:check} using the merged
    prefix.

  \end{enumerate}
  We can sort an entire sequence of length \(n\) by sorting a prefix of length
  at least \(n\).  This algorithm is called \emph{Shivers sort}, after its
  creator's mother.  Implement Shivers sort for lists and for arrays.  The
  executable files \texttt{shivers-sort-list} and \texttt{shivers-sort-array}
  must read a JSON sequence of integers from \texttt{stdin} and write the
  corresponding sorted JSON sequence of integers to \texttt{stdout}.

  \paragraph{Extra Credit:} (2 points)  What are the best-case and worst-case
  running times of Shivers sort in \(\Theta\)-notation?  You may choose the
  version for lists or for arrays, but you must provide both running times and
  an informal argument for each to get any extra credit.

  \paragraph{Extra Credit:} (2 points) What is the worst-case running time of
  Shivers sort when step~\ref{step:recur} recursively sorts a prefix of length
  \(k\) rather than \(\lfloor\nicefrac{k}{2}\rfloor\)?  Provide an informal
  argument and describe what kind of inputs cause this worst-case performance.
\end{problem}

\insolution{
  \begin{solution}
    See code, again.
  \end{solution}
}

\exercise[(10 points)]

\begin{problem}
  Show that there is no comparison sort whose running time is \(O(n)\) for at
  least half of the \(n!\) inputs of length \(n\).  What about a fraction
  \(\nicefrac{1}{n}\) of the inputs of length \(n\)?  What about a fraction
  \(\nicefrac{1}{2^n}\)?
\end{problem}

\insolution{
  \begin{solution}
    The argument for why comparison sorts take \(O(n \lg n)\) is based on the
    fact that a decision tree with \(n!\) leaves has depth at least \(\lg
    (n!)\), which is \(O(n \lg n)\).  For each fraction \(\nicefrac{1}{f(n)}\)
    of the \(n!\) solutions, we must prove that \(\lg \nicefrac{n!}{f(n)} = \lg
    n! - \lg f(n)\) is \(O(n)\).  The largest \(f(n)\) in the problem is
    \(2^n\); \(\lg 2^n = n\).  But \(\lg n! - n = O(n\lg n)\).
    None of these fractions of \(n!\) yield a small enough set of inputs for a
    running time of \(O(n)\).
  \end{solution}
}

\end{document}