% \def\solutionMode{TRUE}
\documentclass[11pt]{article}%
\usepackage{573}
%
% ======================================================================
\begin{document}
% \thispagestyle{empty}
% \headers{\Course{}}{Homework 0 (due 8/30/07)}{\Semester{}}
\begin{center} {\LARGE\bf \Course{}: \CourseName{}, \Semester{}}
\\[1ex]
{\Large\bf Homework 0, due Monday, September 2, 23:59:59, \Year{}}
\\[0.25in]
\end{center}
{%
\begin{center}%
\LARGE \begin{tabular}{|p{1in}|p{2in}|}%
\hline {Name:} & \\
\hline Net ID: & \\
\hline
\end{tabular}
\end{center}
\bigskip \noindent%
Neatly print your name (first name first, with no comma), your
network~ID, and a short alias into the boxes above. \textbf{Do not
sign your name.} \textbf{Do not write your Social Security
number.} Staple this sheet of paper to the top of your
homework.
% ----------------------------------------------------------------------
\bigskip\hrule\bigskip \noindent This homework tests your
familiarity with the prerequisite material from CS 173, CS 225, and
CS~373---many of these problems have appeared on homeworks or exams
in those classes---primarily to help you identify gaps in your
knowledge. \textbf{You are responsible for filling those gaps on
your own.} Chapters 1--6 of CLR should be sufficient review,
but you may want to consult other texts as well.
% ----------------------------------------------------------------------
\bigskip\hrule\bigskip \noindent Before you do anything else, read
the Homework Instructions and FAQ on the \Course{} course web page
(\url{http://courses.engr.illinois.edu/cs573/fa2013/faq/}), and
then check the box below. This web page gives instructions on how
to write and submit homeworks---staple your solutions together in
order, write your name and netID on every page, don't turn in
source code, analyze everything, use good English and good logic,
and so forth. \bigskip\noindent
\centerline{\large\fbox{$\quad\,\,\strut$}~ \Large I have read the
\Course{} Homework Instructions and FAQ.}
\medskip \bigskip\hrule\bigskip
\centerline{\textcolor{red}{\Large \bf Remember to do the quiz on
moodle!}}%
\bigskip\hrule\bigskip }
% \newpage%
% \thispagestyle{empty}%
\Version{1.04}%
\bigskip
\fbox{
\begin{minipage}{0.9\linewidth}
``Be that as it may, it is to night school that I owe what
education I possess; I am the first to own that it doesn't
amount to much, though there is something rather grandiose
about the gaps in it.'' -- The tin drum, Gunter Grass
\end{minipage}
}
\section*{Required Problems}
% ======================================================================
\begin{compactenum}[\color{red} \huge \bf 1.]%
% \begin{enumerate}
% ----------------------------------------------------------------------
% ----------------------------------------------------------------------
\item \HWProblem{60}{Moving numbers revisited.}{
\begin{compactenum}[(A)]
\item \points{30} The input is a multiset $X$ of $n$
positive integer numbers. Consider the following famous
algorithm:
\medskip
\begin{algorithmEnv}
\Algorithm{PlayItSam}$(X):$\+ \\
\While $X$ contains more than two elements \Do \+\\
Three distinct elements $x_1, x_2$ and $x_3$ are chosen
arbitrarily from
$X$,\\
\>such that $x_1 \leq x_2 \leq x_3$\\
\If $x_1 = x_2$ \Then \\
\> $X \leftarrow \pth{X \setminus \brc{x_1, x_2}} \cup
\brc{x_1 + x_2}$\\
\> \Continue\\
\If $x_2 \geq x_3 -1$ \Then \\
\> $X \leftarrow \pth{X \setminus \brc{x_2, x_3}} \cup
\brc{x_2 + x_3}$\\
\> \Continue\\
$X \leftarrow \pth{X \setminus \brc{ x_1, x_2, x_3}}
\cup \brc{ x_1+1, x_2+1, x_3-2}$
\\[-0.2cm]
\end{algorithmEnv}
\medskip
\textbf{Prove} (maybe using induction, but you do not have
to) that \Algorithm{PlayItSam} always terminates.
\item \points{30} (Harder.) Let $N = \sum_{x \in X} x$, and
let $n= \cardin{X}$. Provide an upper bound, as tight as
possible, using $n$ and $N$ on the running time of
\Algorithm{PlayItSam}.
\end{compactenum}
}{}{}
\item \HWProblem{20}%
{Snake in a tournament.}{%
A \emphi{tournament} is a directed graph with exactly one edge
between every pair of vertices. (Think of the nodes as players
in a round-robin tournament, where each edge points from the
winner to the loser.) A \emphi{Hamiltonian path} is a sequence
of directed edges, joined end to end, that visits every vertex
exactly once. Prove that every tournament contains at least
one Hamiltonian path.
\begin{center}\footnotesize\sf
\includegraphics[height=1.5in,width=1.5in]{figs/tournament}\\
A six-vertex tournament containing the Hamiltonian path
$\mathsf{6\to4\to5\to2\to3\to1}$.
\end{center}~ }{}{}{}
\item%
\HWProblem{20}%
{Some probability required.}%
{%
There are $n$ balls (numbered from $1$ to $n$) and $n$ boxes
(numbered from $1$ to $n$). We put each ball in a randomly
selected box.
\begin{compactenum}[(A)]
\item \points{4} A box may contain more than one ball. Let
$S$ be the set of all the labels written on boxes that are
not-empty. Let $X$ be the smallest number in $S$. What is
the expectation of $X$?
\item \points{4} What is the expected number of bins that
have exactly one ball in them? (Hint: Compute the
probability of a specific bin to contain exactly one ball
and then use some properties of expectation.)
\item \points{8} We put the balls into the boxes in such a
way that there is exactly one ball in each box. If the
number written on a ball is the same as the number written
on the box containing the ball, we say there is a
match. What is the expected number of matches?
\item \points{4} What is the probability that there are
exactly $k$ matches? ($1 \leq k < n $)
\end{compactenum}
[Hint: If you have to appeal to ``intuition'' or ``common
sense'', your answers are probably wrong!]%
}{}{}{}
\end{compactenum}
\end{document}