\documentclass[12pt]{article}
\input{macros-course}

\newcommand{\relsub}[2]{\,#1_{#2}\,}

%% Latex asks whether or not to include solutions
%\askaboutsolutions
\askaboutsolutions

\begin{document}

%% PSET 5: Trees, Structural Induction (Rad Fall01)
\ifshowsolutions
  \psetsol{5}{October 12, 2001}{\stamp}
\else
  \pset{5}{October 1, 2001}{Wednesday 10/10, beginning of lecture}{\stamp}
\fi

\ifshowsolutions
{} %
\else
\emph{You MUST include a \textbf{collaboration statement} and your
\textbf{TA's name} on the first page of your solutions.}
\fi

\textbf{Reading:} Rosen \S 8.1, 8.2, 8.5, Lecture Notes 5.

\begin{problems}

%--------------------------------------
% source: new problem by radhika, fall 01
% topics: cut-edge, trees

\problem An edge of a connected graph is called a {\em cut-edge} if
removing the edge disconnects the graph.

\begin{figure}[h]
\begin{center}
\begin{picture}(120,40)

% top row
% line start/slope/length
\put(00,40){\circle*{3}}  \put(00,40){\line(1,0){40}}
                          \put(00,40){\line(1,-1){20}}
\put(40,40){\circle*{3}}  \put(40,40){\line(1,-1){20}}
                          \put(40,40){\line(-1,-1){20}}
\put(100,40){\circle*{3}} \put(100,40){\line(0,-1){40}}
                          \put(100,40){\line(1,-1){20}}
% second row
\put(20,20){\circle*{3}} \put(20,20){\line(0,-1){20}}
\put(60,20){\circle*{3}} \put(60,20){\line(1,0){60}}
                         \put(60,20){\line(0,-1){20}}
\put(120,20){\circle*{3}} \put(120,20){\line(-1,-1){20}}

% bottom row
\put(20,00){\circle*{3}} \put(20,00){\line(1,0){40}}
\put(60,00){\circle*{3}}
\put(100,00){\circle*{3}}

% put A and B
\put(50,30){A}
\put(75,10){B}

\end{picture}
\end{center}
%%\centerline{The line graph $L_4$}
%%\label{fig:cut}
\end{figure}

\ppart In the above figure, are either A or B cut-edges? Explain.

\solnospace{
A is not a cut-edge, B is.

If we remove the edge A the two vertices remain connected because
there is another path between those vertices. If we remove B there is
no path from the end vertices to each other, hence the vertices get
disconnected thus disconnecting the graph.

More succinctly, A is part of a cycle and B is not.

}

\ppart Prove that in a tree every edge is a cut-edge.

\solnospace{There are many ways to prove this. We will prove this by
first proving the following lemma.

Lemma: In a connected graph, an edge $e$ is a cut-edge \emph{if and
only if} no simple cycle contains $e$.

\begin{proof}
Since the lemma has an {\em if and only if} we need to prove both
sides of the implication --- that if an edge is part of a simple cycle
then it can not be a cut-edge, and if an edge is not part of a simple
cycle then it must be a cut-edge. We will use both directions of this
implication to prove parts b) and c).

First, we prove that if $e$ is contained in a simple cycle, then $e$
is not a cut-edge.  Since $G$ is connected, there exists a path $P$
between every pair of distinct vertices $u$ and $v$.  We must show
that there still exists a path between $u$ and $v$ after edge $e$ is
removed.  Let $e, e_1, e_2, \ldots, e_n$ be the edges in a simple
cycle containing $e$.  Since the cycle is simple, none of the edges
$e_1, e_2, \ldots, e_n$ are equal to $e$.  Therefore, we can construct
a new path that connects $u$ and $v$, but does not contain edge $e$ by
substituting either $e_1, e_2, \ldots, e_n$ or $e_n, e_{n-1}, \ldots,
e_1$ in place of edge $e$ in the path $P$.This shows that the graph
remains connected after edge $e$ is removed, and so edge $e$ is not a
cut-edge.

%%% IT seems that we're talking about undirected graphs, so the
%%% following sentence is irrelevant,
%(Which sequence is
%substituted for edge $e$ depends on the direction in which the path
%$P$ traverses the edge $e$.)  

Next, we prove that if $e$ is not a cut-edge, then $e$ is contained in
a simple cycle.  We will make use of Theorem 1 on page 469 of Rosen
(p.464 in ed.3), which states that there is a {\em simple} path
between every pair of distinct vertices in a connected graph.  Since
$e$ is not a cut-edge, the graph obtained by removing edge $e$ is
connected.  So by the theorem, there exists a simple path $P$
connecting the endpoints of edge edge $e$ even after edge $e$ is
removed from the graph.  Adjoining edge $e$ to path $P$ gives a simple
cycle containing edge $e$.
\end{proof}

Given this lemma, we can simply state that since a tree is acyclic,
every edge is a cut-edge.
}

\ppart Prove that in a $n \times n$ mesh (Rosen, pg 452) no edge is
a cut-edge.

\solnospace{
When $n=1$, the claim is trivially true because the mesh
contains no edges.

For $n>1$, every edge is part of a cycle: consider a horizontal edge
between adjacent nodes $a_1, a_2$ on the same row.  Consider the two
nodes $b_1, b_2$ either immediately above or immediately below $a_1,
a_2$.  Then $b_1$ is connected to $b_2$ (adjacent nodes on same row);
$a_1$ is connected to $b_1$ and $a_2$ is connected to $b_2$ (adjacent
nodes on same column).  So $a_1-b_1-b_2-a_2$ forms a cycle. Likewise,
every vertical edge is part of a square cycle.  So every edge is part
of a cycle, and hence cannot be a cut-edge.

Cut-edges can be an important concept because they point out weak
points that can cause total failure --- consider the graph of utility
lines or a network of processors in a parallel computer}

% pset 5, #8
\problem A \emph{minimum spanning tree} in a connected weighted graph
$G$ is a spanning tree in $G$ with the property that no other spanning
tree in $G$ has a lower total weight. Show that an edge with smallest
weight in a connected weighted graph must be part of any minimum
spanning tree. Assume that the smallest weight edge is unique.

%% Show that any minimum spanning tree must contain an edge with the
%% smallest weight.

\solnospace{Suppose that an edge $e$ with smallest weight is not
included in some minimal spanning tree; in other words, suppose that
the minimum spanning tree $T$ contains only edges with weights larger
than that of $e$. If we add $e$ to $T$, (thereby completing the unique
path that already exists between the endpoints of $e$) then we will
obtain a graph with exactly one simple circuit, which contains $e$. We
can then delete some other edge in the circuit, without disconnecting
any of the vertices in that circuit. This results in a spanning tree
with weight strictly less than that of $T$ (since all the other edges
have larger weight than $e$ has). This is a contradiction to the fact
that $T$ is a minimum spanning tree. Therefore, an edge with smallest
weight must be included in $T$.}


%--------------------------------------
% source: Fall 2000  Problem Set 4, Rosen 8.2 exercise 8
% topic: decision trees

\problem How many weighings using a balanced scale are needed in order to
find a counterfeit coin among eight coins if the the counterfeit coin
is either heavier or lighter than the others?  Describe an algorithm
to find the counterfeit coin using this number of weighings.

\solnospace{
Decision tree theory applied naively says that at least $log_{3}8=2$
weighings are needed, but in fact at least 3 weighings are needed. To
see this, consider what the first weighing might accomplish. We can
put one, two or three coins in each pan. If we put one in each pan,
and the scale balances, what we know is that the counterfeit must be
among the remaining 6. Similarly, if we put 2 and the scale balances,
we narrow down our list of suspects to the remaining 4. If we put 3 in
each pan and the scale balances, we are in really good shape, but what
if it doesn't? Then our list of suspects will be the 6 coins in the
scale. What this means is that however many coins we choose to put on
each pan (1,2 or 3), there's always a case where the list of suspects
after the first weighing will be $\geq 4$. One weighing is not enough
to distinguish the counterfeit from among a list of 4 suspects.

% In Tutorial 1, we showed that we can solve a bigger problem (12 coins)
% with three weighings, so we should be able to solve this one with the
% same number of weighings. So if we are lazy and we want to just use
% the algorithm we came up with in Tutorial, we just add 4 good coins to
% our collection and apply that algorithm.

However, a solution is available: Put two coins in each pan. If the
scale balances, then the search is reduced to the other four coins. If
the scale does not balance, then the counterfeit is among the four
coins on the scale. In both cases, after 1 weighing we have cut down
our list of suspects to 4. Call them A, B, C, D. First compare coins A
and B. If they balance, then the counterfeit must be among the other
2. In this case, compare C with A (which we now know must be good). If
they balance, then D is counterfeit. If not, C is counterfeit. On the
other hand, if A and B do not balance, then one of them is the
counterfeit. Compare A with C (which we know must be good). If they
balance, B is the counterfeit. If they do not, A is the counterfeit.
}

%-----------------------------------------
% source: rosen 8.5.36
% pset 5, #7

% \problem Let $T_1$ and $T_2$ be spanning trees of a graph. The
% \textbf{distance} between $T_1$ and $T_2$ is the number of edges in
% $T_1$ and $T_2$ that are not common to $T_1$ and $T_2$. Suppose that
% $T_1, T_2$ and $T_3$ are spanning trees of the simple graph $G$. Show
% that the distance between $T_1$ and $T_3$ does not exceed the sum of
% the distance between $T_1$ and $T_2$ and the distance between $T_2$
% and $T_3$.

% \solnospace{Suppose that $T_1$ contains $a$ edges that are not in
% $T_2$, so that the distance between $T_1$ and $T_2$ is $2a$. Suppose
% that $T_2$ contains $b$ edges that are not in $T_3$, so the distance
% between $T_2$ and $T_3$ is $2b$. Now at worst, the only edges that are
% in $T_1$ and not in $T_3$ are those $a+b$ edges that are in $T_1$ and
% not in $T_2$, or in $T_1$ and $T_2$ but not in $T_3$. Therefore the
% distance between $T_1$ and $T_3$ is at most $2(a+b)$.}


%--------------------------------------
% source: rosen 8.5.28
% topics: backtracking, maze

\problem Rosen \S 8.5 problem 28.

\solnospace{
\problempart
We can use backtracking in the following way:
\begin{itemize}
\item Begin at the starting position and mark it as traveled.
\item At each stage, mark the current position and then chack the 4
  possible directions to go: up, down, right, left.  For each
  direction, check if the new position in that direction is not
  blocked and has not been traveled yet.
\item If there is a direction in which travel is possible, travel to
  the new position and repeat.
\item If travel is not possible in any of the four directions (because
  they're blocked or have been previously marked), then backtrack to
  the previous position and repeat.
\item Stop when we reach the exit
\end{itemize}
\problempart
The path is fairly clear by inspection.
}

%---------------------------------------------------
\problem %source: w/new solution spring01 ps3, spring00 ps3
Read the recursive definition of strings over an alphabet
$\Sigma$ in Rosen 3.3, example 10.  Define the {\em reversal} of a
  string $w$, written $w^R$, as follows:
\begin{itemize}
\item $\lambda^R = \lambda$
\item if $w=vx$ where $v \in \Sigma^*$ and $x \in \Sigma$, then $w^R \
=  xv^R$
\end{itemize}
Prove that for any $s,t \in \Sigma^*$, $(st)^R = t^Rs^R$

\solnospace{
We use structural induction. Specifically, the induction is on $t$ in
the assertion.

For the base case, we must show $\forall s\in\Sigma^*$, $(s\lambda
)^R=\lambda^Rs^R$---but this is clear since the left side is $s^R$ and
the right side is $s^R$ (because $\lambda$ is the empty string).

Now we must show that if for an arbitrary $t\in\Sigma^*$, we have that
$\forall s\in\Sigma^*$, $(st)^R=t^Rs^R$, then $\forall
s\in\Sigma^*,x\in\Sigma$, $(s(tx))^R=(tx)^Rs^R$. We have
$(s(tx))^R=(st(x))^R=x(st)^R$, the last equality by the second
property of reversal. But $x(st)^R=xt^Rs^R$ by the structural
inductive assumption and $xt^Rs^R=(tx)^Rs^R$ again by the second
property.

{\bf Alternative solution:} Alternatively we can prove this by
ordinary induction on the length of the string. But this in fact leads
to a much longer and complicated proof, compared to our structural
induction proof. This is because the recursive structural definition
of the string translates naturally into a simple structural induction
proof.

\begin{proof}
\newline
by strong induction on the length, $n$, of $vw$.
\newline
\begin{tabbing}
XXti\=XXti\=XXti\=XXXXXXXXXXXXXX\=    \kill
\textbf{Base:} $vw$ is of length 0.  Here, $vw = \lambda$ which means $v = w = \lambda$, so $(vw)^R = (\lambda)^R = \lambda = \lambda \lambda = w^Rv^R$.\\
\textbf{Inductive step: Assume:} $P(n): \forall i \in \naturals \; (0 \leq i \leq n)$ $Q(i)$ holds (Inductive Hypothesis).\\
\> That is, $Q(i): ``(vw)^R = w^Rv^R \; for \; an \; arbitrary \; string \; vw \; of \; length \; i''$ \\
We now \textbf{prove} $P(n+1)$ holds.\\
Let $vw$ be an arbitrary string of length $n+1$.\\
\> \textbf{Case 1:} $w$ is of length exactly 0\\
\> \> then $(vw)^R = (v)^R = \lambda v^R = \lambda^R v^R = w^Rv^R$.\\
\> \textbf{Case 2:} $w$ is of length exactly 1\\
\> \> then $v \in \Sigma^*$ and $w \in \Sigma$ ($w$ is a single symbol)\\
\> \> $(vw)^R = wv^R$ by the definition of \emph{reversal}\\
\> \> then $w = w^R$ as $w^R = (\lambda w)^R = w \lambda^R = w$ by definition of \emph{reversal} for a single symbol\\
\> \> so $(vw)^R = w^Rv^R$\\
\> \textbf{Case 3:} $w$ is of length $> 1$ and $\leq n$\\
\> \> then $v \in \Sigma^*$ and has length $\geq 1$\\
\> \> $x \in \Sigma^*$ and $y \in \Sigma$ for some $x$, $y$, s.t. $w = xy$\\
\> \> thus, $vw = vxy$ for some $y \in \Sigma$\\
\> \> let $t = vx$  then, $t \in \Sigma^*$ and is of length $n$ by the definition of \emph{length}\\
\> \> then, $vw = ty$ so that $(vw)^R = (ty)^R = yt^R$ by the definition of \emph{reversal}\\
\> \> we know that $t^R = (vx)^R = x^Rv^R$ by the Inductive Hypothesis at $n$.\\
\> \> so, $(vw)^R = yx^Rv^R = y^Rx^Rv^R$ by substitution and $y = y^R$ for a single symbol.\\
\> \> we have that $y^Rx^R = (xy)^R = w^R$ by the Inductive Hypothesis at some $i \leq n$\\
\> \> thus, $(vw)^R = w^Rv^R$.\\
\> \textbf{Case 4:} $w$ is of length $n+1$\\
\> \> we have in this case that $v = \lambda$\\
\> \> thus, $(vw)^R = (\lambda w)^R = (w)^R = w^R\lambda = w^R\lambda^R = w^Rv^R$\\
$QED$\\
\end{tabbing}
\end{proof}
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% wellordering - recursive sets
% pset 2, #8
\problem Let $a,b$ be integers, and assume at least one of $a$ and $b$
is nonzero.  Define a set $L_{a,b} \subseteq \integers$ inductively as
follows:
\begin{itemize}
\item $a,b \in L_{a,b}$.
\item If $c,d \in L_{a,b}$, then $c+d \in L_{a,b}$.
\item If $c \in L_{a,b}$, then $cn \in L_{a,b}$ for all $n\in\integers$.
\end{itemize}

Do the following parts without appealing to the result of Problem Set 2,
problem 7.

\bparts

\ppart %(a)

Show by induction on the definition of $L_{a,b}$ that any common
divisor of $a$ and $b$ also divides every member of $L_{a,b}$.

\solnospace{
\begin{proof}
The induction hypothesis $P(c)$ is ``any common divisor of $a$ and $b$
also divides $c$.''

\emph{Base case}: $P(a)$ is immediate, since any common divisor of $a$ and
$b$ certainly divides $a$.  Likewise for $P(b)$.

\emph{($c+d$) case}: Assuming $P(c)$ and $P(d)$, we must prove
$P(c+d)$.  So suppose $e$ is a common divisor of $a$ and $b$.  Then $e
\mid c$ by hypothesis $P(c)$ and $e \mid d$ by hypothesis $P(d)$.  That
is, $c = ef$ and $d=eg$ for some $f,g \in \integers$.  Hence $c+d = ef+eg=
e(f+g)$ so $e \mid c+d$, namely $P(c+d)$.

\emph{($cn$) case}: Assuming $P(c)$ and $n \in \integers$, we must
prove $P(cn)$.  So suppose $e$ is a common divisor of $a$ and $b$.  Then
$e \mid c$ by hypothesis.  Hence $e \mid cn$, namely $P(cn)$.
\end{proof}
}

\ppart %(b)

Show that if $c,d \in L_{a,b}$ and $c= dq + r$ for some $q,r \in
\integers$, then $r \in L_{a,b}$.

\solnospace{Since $d \in L_{a,b}$, we have $d(-q) \in L_{a,b}$ by
the ($nc$) case.  Then since $c \in L_{a,b}$, we have $c + d(-q) = r \in
L_{a,b}$ by ($c+d$) case.}

\ppart %(c)

Show that there is a positive integer $g \in L_{a,b}$ which divides every
member of $L_{a,b}$.  \hint Show that there is a least positive member of
$L_{a,b}$.

\solnospace{At least one of the integers $a, -a, b, -b \in L_{a,b}$ must be
positive.  Hence by the well-ordering principle, there is a least positive
integer $g \in L_{a,b}$.

Suppose $c \in L_{a,b}$.  We must show that $g \mid c$.

We prove this by contradiction: if $g$ does not divide $c$, then the
remainder of $c$ divided by $g$ is a positive number smaller than $g$,
which by the previous part is in $L_{a,b}$, contradicting the fact that
$g$ is the smallest such integer.
}

\ppart %(d)

Conclude that $g = \gcd(a,b)$.

\solnospace{By part (a), any common divisor of $a$ and $b$ divides $g$.
Also, since $a,b \in L_{a,b}$, part (c) implies $g$ is a common divisor of
$a$ and $b$, which implies $g$ is the greatest common divisor.}

\ppart Conclude that $\gcd(a,b) = ax+by$ for some $x,y \in \integers$.

\solnospace{It's easy to prove by structural induction that every element of
$L_{a,b}$ is equal to $ax + by$ for some $x,y \in \integers$, so $g$ is
of this form.}

\eparts

%-------------------------------------------------------
% source: pRepository, old fall99 problem
% topic: wel-ordering, structural induction

\problem Suppose we start with a sequence of fully parenthesized
arithmetic or Scheme expressions, and then erase all the alphanumeric
characters other than parentheses.  The result is a string of
parentheses which ``match up''.

For example, erasing non-parenthesis characters from the expression
\texttt{(if (or x y) u v)} leaves the string \texttt{(())}.  Similarly,
erasing non-parentheses from the sequence of three arithmetic expressions
\[
\texttt{(x * x), (y + (3 * (z - 9))), ((x + y) * (u + w))}
\]
leaves the string
\[
\texttt{()((()))(()())}.
\]
On the other hand, even though the string \texttt{())(()} has an equal
number of left and right parentheses, it cannot be obtained by erasing in
this way---because the two middle parentheses don't match up.  Also, no
string of parentheses which begins with a right parenthesis or ends with a
left parenthesis can match up.

We can give an inductive definition of the set, SMU, of ``Strings which
Match Up'', as follows:

\begin{itemize}
\item The empty string (consisting of no parentheses) is an SMU.

\item If $s$ and $t$ are SMU's, then the string $\texttt{(}s\texttt{)}t$
is an SMU.  That is, the new string starts with a left parenthesis which
is followed by the parenthesis characters in the string $s$, followed by a
right parenthesis, followed by the parenthesis characters in the string
$t$.

\end{itemize}


There is a simple test to determine whether a string of parentheses is an
SMU: starting with zero, read the string from left to right adding one for
each left parenthesis and -1 for each right parenthesis.  A string
\emph{counts well} when the count never goes negative and is back to zero
by the end of the string.  Let CW be the set of strings of parentheses
which Count Well.

\bparts
\ppart Prove that CW contains SMU.

\solution{We prove by induction on the definition of SMU (that is,
structural induction) that every element of SMU counts well, so SMU is
contained in CW.  The induction hypothesis is
\[
P(s) ::\equiv s \in \mbox{CW}.
\]
\begin{proof}

{\bf Base Case}: $P(\mbox{empty string})$ holds since the count of the
empty string ends when it starts at zero.

{\bf Inductive Step:} Assume $P(s)$ and $P(t)$ are true.  We need to show
that $P(\texttt{(}s\texttt{)}t)$ is true.

The count values for $\texttt{(}s\texttt{)}t$ start with 0.  Reading the
initial left parenthesis yields 1 as the next count value.  This 1 serves
as the start of a series of count values exactly equal to the count values
of $s$, with each value incremented by one.  Since $s \in \mbox{CW}$ by
hypothesis, these incremented count values begin with 1, always stay
positive, and end with 1.  The right parenthesis immediately after $s$
reduces the ending count to 0.  This 0 serves as the start of the
remaining count values which are exactly the count values of $t$.  Since
$t \in \mbox{CW}$, these remaining values never go negative and end at 0.
Hence the entire sequence of count values for $\texttt{(}s\texttt{)}t$
starts with 0, never goes negative, and ends with 0, which proves that
$\texttt{(}s\texttt{)}t \in \mbox{CW}$.
\end{proof}}

\ppart Conversely, prove that SMU contains CW.

\solution{We show that every string $r\in \mbox{CW}$ is an SMU by
strong induction on the length of $r$.  The induction hypothesis is
\[Q(n) ::\equiv \forall r \in \mbox{CW}(\mbox{if $r$ is length $n$, then
$r \in \mbox{SMU}$}).\]
\begin{proof}

{\bf Base Case} $n = 0$: In this case there is only one string of length
$n$, namely the empty string, which is in SMU by definition, proving
$Q(0)$.

{\bf Inductive Step:} Assume that $Q(k)$ is true for all $k\leq n$, we
need to prove that $Q(n+1)$ is also true.

So suppose $r$ is a length $n+1$ string that counts well.  We must prove
that $r \in \mbox{SMU}$.

Now since $r$ counts well, it must start with a left parenthesis (or else
the count would immediately go negative).  Likewise, since the count for
$r$ returns to the value 0 by the end, $r$ must end with right
parenthesis.  So there must be a \emph{first} right parenthesis in $r$
after which the count returns to 0.  Let $s$ be the substring of $r$
between the initial left parenthesis and this right parenthesis.  So
\[
r = \texttt{(}s\texttt{)}t
\]
for some string $t$.

Since counts only change by one as each parenthesis character is read, and
the count for $r$ \emph{first} returns to 0 after the right parenthesis
following $s$, the count during $s$ must start and end with 1 and must
stay \emph{positive} in between.  But this implies that a count for $s$
alone, which would start with 0, would also end with 0 and stay
\emph{nonnegative} in between.  That is, $s$ by itself counts well.  Since
the length of $s \in \mbox{CW}$ is less than the length of $r$, we have by
strong induction that $s \in \mbox{SMU}$.

Further, we know the count for $r$ returns to 0 after the right
parenthesis following $s$, and since $r \in \mbox{CW}$, the count ends
with 0 again and stays nonnegative in between.  But this implies that $t$
counts well, and since the length of $t$ is less than the length of $r$,
we have by strong induction that $t \in \mbox{SMU}$.  Now by the second
case in the definition of SMU, we conclude $\texttt{(}s\texttt{)}t$,
namely $r$, is in SMU.
\end{proof}}

\eparts



\end{problems}
\end{document}                            

