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