#LyX 1.6.2 created this file. For more info see http://www.lyx.org/
\lyxformat 345
\begin_document
\begin_header
\textclass article
\begin_preamble
\usepackage{fancyheadings}\usepackage{enumerate}\usepackage{xspace}
\chead{CS 4104 (Fall 2009): Homework 4}
\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}
\usepackage{tmax}
\end_preamble
\use_default_options false
\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
\use_hyperref false
\papersize default
\use_geometry false
\use_amsmath 0
\use_esint 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
\author ""
\end_header
\begin_body
\begin_layout Title
\begin_inset VSpace -0.5in
\end_inset
\series bold
Homework 4
\end_layout
\begin_layout Author
CS 4104 (Fall 2009)
\end_layout
\begin_layout Date
Assigned on Monday, September 28, 2009.
\begin_inset Newline newline
\end_inset
Hardcopy due at the beginning of class on Monday, October 5, 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 ̂2
\begin_inset Quotes erd
\end_inset
.
\emph default
Students using LaTeX
\begin_inset space \space{}
\end_inset
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.
Explain your algorithm in words.
A step-wise description is fine.
\emph on
However, if you submit detailed pseudo-code without an explanation, we will
not grade your solutions.
\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.
\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 (35 points) Let
\begin_inset Formula $G=(V,E)$
\end_inset
be an undirected graph and let
\begin_inset Formula $c:E\rightarrow\reals^{+}$
\end_inset
be a function specifying the costs of the edges.
Assume that no two edges have the same cost.
Given a set
\begin_inset Formula $S\subset V$
\end_inset
, where
\begin_inset Formula $S$
\end_inset
contains at least one element and is not equal to
\begin_inset Formula $V$
\end_inset
, let
\begin_inset Formula $e_{S}$
\end_inset
denote the edge in
\begin_inset Formula $E$
\end_inset
defined by applying the cut property to
\begin_inset Formula $S$
\end_inset
, i.e.,
\begin_inset Formula \[
e_{S}={\arg\min}_{e\in\emph{cut}(S)}c_{e}.\]
\end_inset
In this definition, the function
\begin_inset Formula $\arg\min$
\end_inset
is just like
\begin_inset Formula $\min$
\end_inset
but returns the argument (in this case the edge) that achieves the minimum.
Let
\begin_inset Formula $F$
\end_inset
be set of all such edges, i.e.,
\begin_inset Formula $F=\{e_{S},S\subset V,S\not=\emptyset\}$
\end_inset
.
Answer the following questions, providing proofs for all but the first
question.
\end_layout
\begin_deeper
\begin_layout Standard
[(i)]
\end_layout
\begin_layout Enumerate
(5 points) How many distinct cuts does
\begin_inset Formula $G$
\end_inset
have?
\end_layout
\begin_layout Enumerate
(10 points) Consider the graph induced by the set of edges in
\begin_inset Formula $F$
\end_inset
, i.e., the graph formed by
\begin_inset Formula $G'=(V,F)$
\end_inset
.
Is
\begin_inset Formula $G'$
\end_inset
connected?
\end_layout
\begin_layout Enumerate
(10 points) Does
\begin_inset Formula $G'$
\end_inset
contain a cycle?
\end_layout
\begin_layout Enumerate
(5 points) How many edges does
\begin_inset Formula $F$
\end_inset
contain?
\end_layout
\begin_layout Enumerate
(5 points) What conclusion can you draw from your answers to the previous
statements?
\end_layout
\begin_layout Standard
\begin_inset ERT
status collapsed
\begin_layout Plain Layout
%
\backslash
solution{
\end_layout
\begin_layout Plain Layout
\end_layout
\end_inset
\end_layout
\begin_layout Standard
\begin_inset ERT
status collapsed
\begin_layout Plain Layout
% }
\end_layout
\begin_layout Plain Layout
\end_layout
\end_inset
\end_layout
\end_deeper
\begin_layout Description
Problem 2 (25 points) Solve exercise 21 in Chapter 4 (page 200) of your
textbook.
Note that you cannot sort the edges, since your algorithm must run in
\begin_inset Formula $O(n)$
\end_inset
time.
(
\emph on
Hint:
\emph default
Use the solution to exercise 2 in Chapter 3 (page 107) of your textbook.
If you like, you can give your algorithm for this exercise some name, e.g.,
\family typewriter
FindCycle
\family default
, and simply use this algorithm as a sub-routine.
You do not have to describe the
\family typewriter
FindCycle
\family default
algorithm.)
\end_layout
\begin_deeper
\begin_layout Standard
\begin_inset ERT
status collapsed
\begin_layout Plain Layout
%
\backslash
solution{
\end_layout
\begin_layout Plain Layout
\end_layout
\end_inset
\begin_inset ERT
status collapsed
\begin_layout Plain Layout
% }
\end_layout
\begin_layout Plain Layout
\end_layout
\end_inset
\end_layout
\end_deeper
\begin_layout Description
Problem 3 (40 points) You are given a graph
\begin_inset Formula $G(V,E)$
\end_inset
and a minimum spanning tree
\begin_inset Formula $(V,T)$
\end_inset
for
\begin_inset Formula $G$
\end_inset
.
You now pick an edge
\begin_inset Formula $e$
\end_inset
in
\begin_inset Formula $E$
\end_inset
and change its cost from
\begin_inset Formula $c$
\end_inset
to
\begin_inset Formula $c'$
\end_inset
.
Describe an algorithm to update
\begin_inset Formula $T$
\end_inset
so that it is a minimum spanning tree for the graph with the new edge weight.
Your algorithm must run in time linear in the number of nodes and edges
in
\begin_inset Formula $G$
\end_inset
.
There are multiple cases to consider, depending on whether
\begin_inset Formula $e$
\end_inset
is in
\begin_inset Formula $T$
\end_inset
or not and whether
\begin_inset Formula $c$
\end_inset
is larger or smaller than
\begin_inset Formula $c'$
\end_inset
.
You may find it useful to describe each case separately.
You can assume that all edge costs are distinct, both before and after
the change.
\end_layout
\begin_deeper
\begin_layout Standard
\begin_inset ERT
status collapsed
\begin_layout Plain Layout
%
\backslash
solution{
\end_layout
\begin_layout Plain Layout
\end_layout
\end_inset
\end_layout
\begin_layout Standard
\begin_inset ERT
status collapsed
\begin_layout Plain Layout
% }
\end_layout
\begin_layout Plain Layout
\end_layout
\end_inset
\end_layout
\end_deeper
\end_body
\end_document