#LyX file created by tex2lyx 1.6.2
\lyxformat 247
\begin_document
\begin_header
\textclass article
\begin_preamble
\usepackage{fancyheadings}\usepackage{enumerate}\usepackage{xspace}
\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}
\end_preamble
\language english
\inputencoding auto
\font_roman default
\font_sans default
\font_typewriter default
\font_default_family default
\font_sc false
\font_osf false
\font_sf_scale 100
\font_tt_scale 100
\graphics default
\paperfontsize default
\spacing single
\papersize default
\use_geometry false
\use_amsmath 0
\cite_engine basic
\use_bibtopic false
\paperorientation portrait
\secnumdepth 3
\tocdepth 3
\paragraph_separation indent
\defskip medskip
\quotes_language english
\papercolumns 1
\papersides 1
\paperpagestyle fancy
\tracking_changes false
\output_changes false
\end_header
\begin_body
\begin_layout Title
\begin_inset VSpace -0.5in
\end_inset
\series bold
Homework 2
\series default
\end_layout
\begin_layout Author
CS 5104 (Fall 2009)
\end_layout
\begin_layout Date
Assigned on Wednesday, September 9, 2009.
\newline
Hardcopy due at the beginning of class on Wednesday, September 16, 2009.
\end_layout
\begin_layout Paragraph
Instructions:
\end_layout
\begin_layout Itemize
Do not forget to typeset your solutions.
\emph on
Every mathematical expression must be typeset as a mathematical expression, e.g., the square of
\begin_inset Formula $n$
\end_inset
must appear as
\begin_inset Formula $n^2$
\end_inset
and not as
\begin_inset Quotes eld
\end_inset
n\i \^{}
2
\begin_inset Quotes erd
\end_inset
.
\emph default
Students using LaTeX\InsetSpace \space{}
or LyX can use the corresponding versions of the homework problems to start entering their solutions.
\end_layout
\begin_layout Itemize
Describe your algorithms as clearly as possible. The style used in the book is fine, as long as your description is not ambiguous.
\end_layout
\begin_layout Itemize
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.
\end_layout
\begin_layout Itemize
Do not describe your algorithms only for a specific example you may have worked out.
\end_layout
\begin_layout Itemize
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 on
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.
\emph default
\end_layout
\begin_layout Itemize
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_layout
\begin_layout Description
Problem 1 (25 points) Solve exercise 2 in Chapter 3 (page 107) of your textbook. Your proof of correctness must consider two cases:
\end_layout
\begin_deeper
\begin_deeper
\begin_layout Standard
[(a)]
\end_layout
\end_deeper
\begin_layout Enumerate
The graph does not contain a cycle: in this case, you should prove that your algorithm correctly reports this fact.
\end_layout
\begin_layout Enumerate
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_layout
\end_deeper
\begin_deeper
\begin_layout Standard
\begin_inset ERT
status collapsed
\begin_layout Standard
%
\backslash
solution{
\end_layout
\begin_layout Standard
\end_layout
\end_inset
\begin_inset ERT
status collapsed
\begin_layout Standard
% }
\end_layout
\begin_layout Standard
\end_layout
\end_inset
\end_layout
\end_deeper
\begin_layout Description
Problem 2 (25 points) Solve exercise 5 in Chapter 3 (page 108) of your textbook. Given a tree
\begin_inset Formula $T$
\end_inset
, let us define two useful quantities:
\begin_inset Formula $c_{T}$
\end_inset
(
\begin_inset Formula $c$
\end_inset
with
\begin_inset Formula $T$
\end_inset
as a subscript) the number of nodes in
\begin_inset Formula $T$
\end_inset
with two children, and
\begin_inset Formula $l_{T}$
\end_inset
(
\begin_inset Formula $l$
\end_inset
with
\begin_inset Formula $T$
\end_inset
as a subscript) the number of leaves in
\begin_inset Formula $T$
\end_inset
. With these two quantities defined, the goal of the problem is to prove that for every tree
\begin_inset Formula $T$
\end_inset
,
\begin_inset Formula $c_{T} = l_{T} - 1$
\end_inset
. 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.
\end_layout
\begin_deeper
\begin_deeper
\begin_layout Standard
[(i)]
\end_layout
\end_deeper
\begin_layout Enumerate
There exists a tree
\begin_inset Formula $T$
\end_inset
on
\begin_inset Formula $n - 1$
\end_inset
nodes such that
\begin_inset Formula $c_{T} =
l_{T} - 1$
\end_inset
.
\end_layout
\begin_layout Enumerate
For every integer
\begin_inset Formula $k$
\end_inset
between
\begin_inset Formula $1$
\end_inset
and
\begin_inset Formula $n - 1$
\end_inset
, there exists a tree
\begin_inset Formula $T$
\end_inset
on
\begin_inset Formula $k$
\end_inset
nodes such that
\begin_inset Formula $c_{T} = l_{T} - 1$
\end_inset
.
\end_layout
\begin_layout Enumerate
For every tree
\begin_inset Formula $T$
\end_inset
on
\begin_inset Formula $n - 1$
\end_inset
nodes,
\begin_inset Formula $c_{T} = l_{T} - 1$
\end_inset
.
\end_layout
\end_deeper
\begin_deeper
\begin_layout Standard
\begin_inset ERT
status collapsed
\begin_layout Standard
%
\backslash
solution{
\end_layout
\begin_layout Standard
\end_layout
\end_inset
\end_layout
\begin_layout Standard
\begin_inset ERT
status collapsed
\begin_layout Standard
% }
\end_layout
\begin_layout Standard
\end_layout
\end_inset
\end_layout
\end_deeper
\begin_layout Description
Problem 3 (20 points) Solve exercise 7 in Chapter 3 (page 108-109) of your textbook.
\end_layout
\begin_deeper
\begin_layout Standard
\begin_inset ERT
status collapsed
\begin_layout Standard
%
\backslash
solution{
\end_layout
\begin_layout Standard
\end_layout
\end_inset
\begin_inset ERT
status collapsed
\begin_layout Standard
% }
\end_layout
\begin_layout Standard
\end_layout
\end_inset
\end_layout
\end_deeper
\begin_layout Description
Problem 4 (30 points) Solve exercise 9 in Chapter 3 (page 110) of your textbook.
\emph on
Hint:
\emph default
Many of the layers in the BFS tree rooted at
\begin_inset Formula $s$
\end_inset
have a special property.
\end_layout
\begin_deeper
\begin_layout Standard
\begin_inset ERT
status collapsed
\begin_layout Standard
%
\backslash
solution{
\end_layout
\begin_layout Standard
\end_layout
\end_inset
\begin_inset ERT
status collapsed
\begin_layout Standard
% }
\end_layout
\begin_layout Standard
\end_layout
\end_inset
\end_layout
\end_deeper
\end_body
\end_document