\documentclass{article}
\usepackage[top=1in,bottom=1in,left=1in,right=1in]{geometry}
\usepackage{fancyheadings,enumerate,xspace}
\pagestyle{fancy}
\chead{CS 4104 (Fall 2009): Homework 2}
\newcommand{\solution}[1]{\textbf{Solution:} #1}
\newcommand{\cut}[1]{\ensuremath{\mathnormal{}{cut}(#1)}}
\newcommand{\calg}{\ensuremath{{\cal G}}\xspace}
\newcommand{\calo}{\ensuremath{{\cal O}}\xspace}
\begin{document}
\title{\vspace{-0.5in}\textbf{Homework 2}}
\author{CS 4104 (Fall 2009)} \date{Assigned on Wednesday, September 9,
2009. \\Hardcopy due at the beginning of class on Wednesday, September
16, 2009.}
\maketitle
\paragraph{Instructions:}
\begin{itemize}
\item Do not forget to typeset your solutions. \emph{Every mathematical
expression must be typeset as a mathematical expression, e.g., the
square of $n$ must appear as $n^2$ and not as ``n\^{}2''.} Students
using \LaTeX\ or LyX can use the corresponding versions of the
homework problems to start entering their solutions.
\item Describe your algorithms as clearly as possible. The style used in
the book is fine, as long as your description is not ambiguous.
\item Do not make any assumptions not stated in the problem. If you do
make any assumptions, state them clearly, and explain why the
assumption does not decrease the generality of your solution.
\item Do not describe your algorithms only for a specific example you
may have worked out.
\item You must also provide a clear proof that your solution is correct
(or a counter-example, where applicable). Type out all the statements you
need to complete your proof. \emph{You must convince us that you can
write out the complete proof. You will lose points if you work out
some details of the proof in your head but do not type them out in
your solution.}
\item Analyse your algorithm and state the running time. You will only
get partial credit if your analysis is not tight, i.e., if the bound
you prove for your algorithm is not the best upper bound possible.
\end{itemize}
\begin{description}
\item[Problem 1] (25 points) Solve exercise 2 in Chapter 3 (page 107) of
your textbook. Your proof of correctness must consider two cases:
\begin{enumerate}[(a)]
\item The graph does not contain a cycle: in this case, you should
prove that your algorithm correctly reports this fact.
\item The graph contains one or more cycles: in this case, you must
prove that the algorithm correctly computes one of the cycles in the
graph. If the graph contains many cycles, it is enough to report one
of the cycles.
\end{enumerate}
% \solution{
% }
\item[Problem 2] (25 points) Solve exercise 5 in Chapter 3 (page 108) of
your textbook. Given a tree $T$, let us define two useful quantities:
$c_{T}$ ($c$ with $T$ as a subscript) the number of nodes in $T$ with
two children, and $l_{T}$ ($l$ with $T$ as a subscript) the number of
leaves in $T$. With these two quantities defined, the goal of the
problem is to prove that for every tree $T$, $c_{T} = l_{T} - 1$. To
assist you with the proof, here are three candidates for the induction
hypothesis. In your solution, state which candidate is correct and
then provide the complete proof by induction based on this choice.
\begin{enumerate}[(i)]
\item There exists a tree $T$ on $n - 1$ nodes such that $c_{T} =
l_{T} - 1$.
\item For every integer $k$ between $1$ and $n - 1$, there exists a
tree $T$ on $k$ nodes such that $c_{T} = l_{T} - 1$.
\item For every tree $T$ on $n - 1$ nodes, $c_{T} = l_{T} - 1$.
\end{enumerate}
% \solution{
% }
\item[Problem 3] (20 points) Solve exercise 7 in Chapter 3 (page 108-109) of your
textbook.
% \solution{
% }
\item[Problem 4] (30 points) Solve exercise 9 in Chapter 3 (page 110) of your
textbook. \emph{Hint:} Many of the layers in the BFS tree rooted at
$s$ have a special property.
% \solution{
% }
\end{description}
\end{document}