\documentclass{article}
\usepackage[top=1in,bottom=1in,left=1in,right=1in]{geometry}
\usepackage{fancyheadings,enumerate,xspace,amssymb}
\pagestyle{fancy}
%\usepackage{cs5114}
% macros useful for handouts and homeworks.
\newcommand{\setcourse}[1]{\newcommand{\course}{#1\xspace}}
\newcommand{\setsem}[1]{\newcommand{\sem}{#1\xspace}}
\newcommand{\sethwnum}[1]{\newcommand{\hwnum}{#1\xspace}}
\setcourse{CS 4104}
\setsem{Spring 2014}
\sethwnum{2}
\chead{\course (\sem): Homework \hwnum}
\newcommand{\reals}{\ensuremath{\mathbb{R}}}
\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 \hwnum}}
\author{\course (\sem)}
\date{Assigned on Monday, February 17, 2014. \\Submit a PDF file
containing your solutions on Scholar by the beginning of class on
Wednesday, February 25, 2014.}
\maketitle
\paragraph{Instructions:}
\begin{itemize}
\item You can pair up with another student to solve the homework. You
are allowed to discuss possible algorithms and bounce ideas with your
team-mate. \textbf{Do not discuss proofs of correctness or running time in
detail with your team-mate.} Please form teams yourselves. Of course,
you can ask me for help if you cannot find a team-mate. You may choose
to work alone. \emph{Each of you must write down your solution
individually, and write down the name of the other member in your
team. If you do not have a team-mate, please say so.}
\item Apart from your team-mate, you are not allowed to consult any
sources other than your textbook, the slides on the course web page,
your own class notes, the TAs, and the instructor. In particular, do
not use a search engine.
\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
can use the \LaTeX\ version 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. Explain your algorithm in words. A step-wise description is
fine. \emph{However, if you submit detailed pseudo-code without an
explanation, we will not grade your solutions.}
\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 Describe an analysis of your algorithm and state and prove 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}