\documentclass[11pt,twoside]{article}    
\usepackage{latex-macros/course}% !! use the macros 

\renewcommand{\coursecopyrightnames}
{\href{http://theory.lcs.mit.edu/~meyer}{Prof.~Albert~R.~Meyer}}

\newcommand{\ms}[1]{\mathop{\text{#1}}}

\providecommand{\ide}{\ms{id}}
\providecommand{\EF}{\ms{F18}}
\providecommand{\T}{\ms{ST}}
\providecommand{\leaves}{\ms{leaves}}
\providecommand{\nodes}{\ms{nodes}}
\providecommand{\makeb}{\ms{makeboth}}
\newcommand{\membern}{\ms{member}}
\newcommand{\makeleft}{\ms{makeleft}}
\newcommand{\makeright}{\ms{makeright}}

\newcommand{\RBT}{\text{RecBinT}}
\newcommand{\FBT}{\text{FullBinT}}
\newcommand{\rt}{\text{root}}
%\newcommand{\rootr}{\text{FinT}}
\newcommand{\CT}{\text{CT}}
\newcommand{\RCT}{\text{RecCT}}

\newcommand{\deriv}{\frac{d}{dx}}
\renewcommand{\paren}[1]{\left(#1\right)}

\newcommand{\PT}{\text{PayT}}

\newcommand{\lub}{\ms{lub}}
\newcommand{\glb}{\ms{glb}}

\newcommand{\mav}{\ms{max-value}}
\newcommand{\miv}{\ms{min-value}}
\newcommand{\subtrees}{\mathcal{S}}


\begin{document} 
\inclassproblems{6, Fri}

\section{Problems}

\begin{problem}

[carried over from Monday, Oct. 7]

The definition of Recursive Ordered Binary Trees, $\RBT$, from Week 6
Notes is repeated in an Appendix. % Definition~\ref{rbt} below.

\bparts

\ppart Give a recursive definition of the set of $\leaves$ of a $\RBT$.

\solution{We can then define the set of leaves, $L_T$, of $T \in \RBT$ as follows:
\begin{enumerate}

\item ($T=(V,E)$ has one vertex.)  $L_T \eqdef V$.

\item ($T = \makeleft(T_1)$.)  $L_T \eqdef L_{T_1}$.

\item ($T = \makeright(T_1)$.)  $L_T \eqdef L_{T_1}$.

\item ($T = \makeb(T_1,T_2)$.)  $L_T \eqdef L_{T_1} \union L_{T_2}$.

\end{enumerate}
}


Full Binary Trees, $\FBT$, are the special case of $\RBT$'s in which only
the $\makeb$ constructor is used.  For example,
Figure~\ref{fig:fullbintree} shows an FBT with 13 nodes of which 7 are
leaves:

\begin{figure}[h]
\begin{center}
\input{figures/fbtree.pic}
\end{center}
\caption{A full binary tree.}
\label{fig:fullbintree}
\end{figure}


\ppart Prove by structural induction on the definition of $\FBT$
that for all $\FBT$'s, $t$,
\[
2\card{\leaves(t)} = \card{\nodes(t)}+1.
\]
\solution{
Let $T, t_1, t_2$ be FBTs. Let $L, \ell_1, \ell_2$ represent their
\emph{number} of leaves and similarly let
$N, n_1, n_2$ represent their number of nodes. We want to prove that for
all FBTs we have: $2L~=~N +1$
\begin{description}
\item[Base case:] When $N=1$ (the tree has only one vertex), then $L=1$
(it has one leaf) and so the claim is true ($2=1+1$). 
\item[Inductive step:] Assume that the claim holds for trees $t_1$ and
$t_2$. We want to prove that $T=\makeb(t_1, t_2)$ also satisfies that
property. We have:
\[
\left.\begin{array}{lll}
2\cdot \ell_1 &=& n_1+1\\
2\cdot \ell_2 &=& n_2+1
\end{array}\right\} \implies
2\cdot (\ell_1 +\ell_2) ~=~ (n_1+n_2+1)+1\implies
2\cdot L ~=~ N+1
\]
So the claim holds for $T$ as well.
\end{description}
}



\eparts
\end{problem}


\begin{problem}

[carried over from Monday, Oct. 7]

The Elementary 18.01 Functions ($\EF$'s) are the set of functions of
one real variable defined recursively as follows:
\begin{enumerate}
\item The identity function, $\ide(x) \eqdef x$ is an $\EF$,\label{identfunc}

\item any the constant function is an $\EF$,\label{const}

\item $\sin, \cos, e^x$ are $\EF$'s,\label{basefunc} 

     and if $f,g$ are $\EF$'s, then so are

\item $f + g$, $f-g$, $fg$, $f/g$\label{+-}

\item the inverse function $f^{-1}$,\label{inversefunc}

\item the composition $f \compose g$.\label{cmp}
\end{enumerate}

Show that the Elementary 18.01 Functions are \emph{closed under taking
derivatives}.  That is, show that if $f$ is an $\EF$, then so is $df/dx$.

\solution{
\begin{proof}
By Structural Induction on def of $\EF$.
\begin{description}

\item[Base Cases:] We want to show that the derivatives of all the
functions mentioned in rules~\ref{identfunc}., \ref{const}.,
\ref{basefunc}.\ are in $\EF$.  This is easy: for example, $d \ide(x)/dx =
1$, and so by rule~\ref{const}., it is in $\EF$.  Similarly, $d \cos(x)/dx
= -\sin(x)$ which is also in $\EF$ since $\sin(x)\in \EF$ by
rule~\ref{basefunc}., and therefore $-\sin(x)$ is as well (by rule
\ref{+-}.).

\item[Induction Case:] ($f^{-1}$).  Assume $f, df/dx \in \EF$ to prove
$d f^{-1}(x)/dx \in \EF$.

Letting $y = f(x)$, so $x=f^{-1}(y)$, we know from Leibniz' rule in
calculus that
\begin{equation}\label{Leib}
df^{-1}(y)/dy = dx/dy = \frac{1}{dy/dx}.
\end{equation}
For example,
\[
d \sin^{-1}(y)/dy = 1/(d \sin(x)/dx) = 1/\cos(x) = 1/\cos(\sin^{-1}(y)).
\]
Stated as in ~(\ref{Leib}), this rule is easy to remember, but can easily
be misleading because of the variable switching between $x$ and $y$.
It's more clearly stated using variable-free notation:
\begin{equation}\label{Leib2}
(f^{-1})' = (1/f') \compose f^{-1}.
\end{equation}
Now, since $f' \in \EF$ (by assumption), so is $1/f'$ (by~\ref{+-}.) and
$f^{-1}$ (by~\ref{inversefunc}.), and therefore so is their composition
(by~\ref{cmp}).  Hence the righthand side of equation~(\ref{Leib2})
defines a function in $\EF$.

\item[Induction Case:] ($f \compose g$).  Assume $f,g, df/dx, dg/dx \in \EF$ to
prove $d(f \compose g)(x)/dx \in \EF$.

The Chain Rule states that
\[
\frac{d(f(g(x)))}{dx} = \frac{d f(g)}{dg}\cdot\frac{dg}{dx}.
\]
Stated more clearly in variable-free notation, this is
\[
(f \compose g)' = (f' \compose g) \cdot g'.
\]
The righthand side of this equation defines a function in $\EF$ by
rules~\ref{cmp}.\ and~\ref{+-}.

The other Induction cases are similar.
\end{description}
\end{proof}
}
\end{problem}


\begin{problem}

\textbf{We didn't get to this problem on Friday, so we'll do it on the pset.}

We can generalize win-lose 2-player terminating games of perfect
information to games with ``payoff'' amounts.  In these games, two players
called the \emph{max-player} and the \emph{min-player} alternate moves
until the game ends with the min-player paying some payoff amount to the
max-player.  How much the min-player pays depends on how the game ends.
Negative payoffs mean the max-player pays the min-player.  The max-player
moves first.

Such games are defined by finite-path trees with leaves labelled with real
numbers.  These are the payoff amounts.  The max-player tries to arrive at
a leaf with as large a payoff as possible, and the min-player tries to
minimize the payoff to the max-player.

\begin{definition*}

The set of payoff-game trees, $\PT$, can be defined recursively as
follows:
\begin{enumerate}

\item If $T$ is a graph with one vertex, $v$, and no edges, then $T$ is a
$\PT$ and $\rt(T) \eqdef v$.

\item if $\subtrees$ is a set of $\PT$'s such that no vertex occurs in
more than one tree in $\subtrees$, and $v$ is a ``new'' element that is
not a vertex of any tree in $\subtrees$, then $T$ is in $\PT$ where
$\rt(T) = v$ and the edges of $T$ are the edges of all the trees in
$\subtrees$ along with edges connecting $\rt(T)$ to the roots of each of
the trees in $\subtrees$.  The trees in $\subtrees$ are called the
\emph{children} of $T$.

\end{enumerate}

\end{definition*}

We define functions $\mav(T)$ and $\miv(T)$ on payoff-game trees, $T \in
\PT$, recursively on the definition of $\PT$:

\begin{enumerate}

\item If $T$ is a single node labelled $r$, then
\[
\mav(T) = \miv(T) \eqdef r.
\]

\item If the nonempty set $\subtrees$ is the set of children of $T$, then
\begin{eqnarray*}
\mav(T) & \eqdef & \lub \set{\miv(S) \suchthat S \in \subtrees}\\
\miv(T) & \eqdef & \glb \set{\mav(S) \suchthat S \in \subtrees}.
\end{eqnarray*}

\end{enumerate}

\bparts

\ppart Suppose a payoff-game tree, $T$, is \emph{finite}.  Prove that
\begin{enumerate}

\item \label{max-first} If the max-player is the first player to move in
$T$, then he has a strategy that guarantees his payoff will be at least
$\mav(T)$, no matter how the min-player behaves.

\item \label{max-second} If the max-player is the second player to move in
$T$, then he has a strategy that guarantees his payoff will be at least
$\miv(T)$.

\item \label{min-first} Likewise, if the min-player is the first player to
move in $T$, then she has a strategy that guarantees the payoff to
max-player will be at most $\miv(T)$.

\item \label{min-second} If the min-player is the second player to move in
$T$, then she has a strategy that guarantees the payoff to max-player will
be at most $\mav(T)$.

\end{enumerate}
(So the players may as well skip playing and just have the min-player pay
$\mav(T)$ to the max-player.)

\solution{To appear in  Problem Set 6-7 solutions.}


\iffalse

\solution{
The max-player's strategy is to move on his turn to the subtree with the
largest $\miv$.  The min-player's strategy is to move to the subtree with
the smallest $\mav$.

By structural induction on the definition of $\mav(T)$ and $\miv(T)$, we
prove~\ref{max-first}.\ and~\ref{max-second}.

\end{enumerate}

\textbf{Base case} ($T$ is a leaf): The game is over with no moves, and
the max-player's payoff is the payoff at the the leaf.  This is $\mav(T)$
by definition of $\mav$.

\textbf{Induction case:} ($T$ has a nonempty set, $\mathcal{S}$, of
(direct) subtrees)

Suppose the max-player moves first in $T$.  Using his strategy, he moves
to $S \in \subtrees$ with the largest $\miv$.  Now in the game defined by
$S$, he moves second.  By induction hypothesis~\ref{max-second}., he has a
strategy in $S$ guaranteeing at payoff at least $\miv(S)$.  Hence, he is
guaranteed a payoff of at least $\max \set{\miv{S} \suchthat S \in
\subtrees}$.  But by definition, this is precisely $\mav(T)$.

A corresponding proof using induction hypothesis~~\ref{max-first} shows
his strategy ensures payoff at least $\miv(T)$ if he moves second in $T$.

A similar proof confirms~\ref{min-first}.\ and ~\ref{min-first}.}

\fi


\ppart Now generalize the previous part to arbitrary $\PT$'s.  \hint It
might be helpful to assume the payoff amounts at the leaves are bounded
above and below by particular numbers.  After settling this case, try it
without assuming bounds.  Note that in the unbounded case, $\mav{T}$ may
be $+\infty$ and $\miv{T}$ may be $-\infty$.

\iffalse
\solution{
In the bounded case, we can say that for any $\epsilon >0$,

\begin{enumerate}

\item the max-player has a strategy that guarantees his payoff will be
\emph{at least} $\mav(T)-\epsilon$,

\item the min-player has a strategy that guarantees the max-player's
payoff will be \emph{at most} $\mav(T) + \epsilon$.

\end{enumerate}

The max-player's strategy is to move on his turn to a subtree, $S_0$, with
\[
\miv(S_0) \ge \lub \set{\miv(S) \suchthat S \in \subtrees} - \epsilon/2,
\]
and then to use his strategy in $S_0$ to guarantee a payoff $\ge \miv(S) -
\epsilon/2$.

The min-player's strategy is to move on his turn to a subtree, $S_1$, with
\[
\mav(S_1) \le \glb \set{\mav(S) \suchthat S \in \subtrees} + \epsilon/2,
\]
and then to use his strategy in $S_1$ to guarantee a payoff $\le \mav(S) +
\epsilon/2$.

The rest of the proof  by structural induction is essentially the same as
for the finite case.
}
\fi


\eparts

\end{problem}

\instatements{
\newpage

\section{Appendix: From Week 6 Notes}

Several basic examples of recursively defined data types are based on
\emph{rooted trees}.  These are possibly infinite directed trees, $T =
(V_T, E_T)$, with a necessarily unique ``root'' vertex $\rt(T)$, such that
every vertex is reachable by a directed path from the root.  Finite-Path
Trees from
\hyperref{http://theory.lcs.mit.edu/classes/6.042/fall02/handouts/lectures/ln5.pdf}
{def}{fptree}{Week 5 Notes}, for example, are the class of rooted trees
which do not have any infinite directed path from the root.

Another important class of trees are the \emph{ordered binary trees}.
These are possibly infinite rooted trees with labelled edges, such that at
most two edges leave each vertex.  If two edges leave a vertex, one is
labelled \texttt{left} and the other is labelled \texttt{right}.  If one
edge leaves a vertex, it is labelled either \texttt{left} or
\texttt{right}.

\begin{definition}\label{rbt}

We will define a special class of ordered binary trees called the \emph{recursive
ordered binary trees}, $\RBT$:

\begin{enumerate}

\item
If $G$ is a graph with one vertex and no edges, then $G$ is a $\RBT$.
That is, $(\set{v}, \emptyset) \in \RBT$ and $\rt((\set{v}, \emptyset)) =
v$.

\item \label{ml}
If $T=(V,E)$ is in $\RBT$, and $\mathbf{n}$ is a ``new'' node not in $V$,
then the graph, $\ms{makeleft}(T)$, made by adding an edge labelled
\texttt{left} from $\mathbf{n}$ to $\rt(T)$ is a $\RBT$.  That is,
\[
\ms{makeleft}(T) \eqdef (V \union \set{\mathbf{n}}, E \union
 \set{(\mathbf{n},\rt(T),\texttt{left})}) \in \RBT,
\]
where $(v,w,\ell)$ is the directed edge from vertex $v$ to
vertex $w$ with label $\ell$.

\item \label{mr} Same as above, with ``right'' in place of ``left.''

\item If $T_1=(V_1,E_1)$ and $T_2=(V_2,E_2)$ are in $\RBT$, $V_1$ and
$V_2$ are disjoint, and $\mathbf{n}$ is a ``new'' node not in $V_1 \union
V_2$, then the graph, $\ms{makeboth}(T_1,T_2)$, made by adding an edge
labelled \texttt{left} from $\mathbf{n}$ to $\rt(T_1)$ and an edge
labelled \texttt{right} from $\mathbf{n}$ to $\rt(T_2)$ is a $\RBT$.
That is,
\end{enumerate}

\[
\ms{makeboth}(T_1,T_2) \eqdef (V_1 \union V_2 \union \set{\mathbf{n}}, E_1
\union E_2 \union \set{(\mathbf{n},\rt(T_1),\texttt{left}),
(\mathbf{n},\rt(T_2),\texttt{right})}) \in \RBT.
\]

These cases are illustrated in Figure~\ref{fig:bintree}, with edges
labelled ``left'' shown going down to the left, and edges labelled
``right'' shown going down to the right.

\end{definition}


\begin{figure}
\begin{center}
\input{figures/btree.pic}
\end{center}
\caption{Building a binary tree: (a)~$\ms{makeleft}(T)$,
(b)~$\ms{makeright}(T)$, and (c)~$\ms{makeboth}(T_1,T_2)$.}
\label{fig:bintree}
\end{figure}


Note that $\RBT$ is precisely the set of \emph{finite} ordered binary
trees.

A special case of $\RBT$'s are the \emph{full} ordered binary trees,
$\FBT$.  These are $\RBT$'s in which every node is either a \emph{leaf}
(\ie has out-degree zero) or has both a left and right subtree (see
Figure~\ref{fig:fullbintree}).  In other words rules~\ref{ml}.\
and~\ref{mr}.\ in the definition of $\RBT$ are not used in defining the
subset $\FBT \subset \RBT$.
}

\end{document}

\iffalse

\begin{problem} 
We define the family $\T$ of \emph{search trees} as follows:
\begin{enumerate}
\item  Any single number $x$ is in $\T$.
\item  If $T$ and $T'$ are in $\T$, and a number $x$ is larger than every
number in $T$ but smaller than every number in $T'$, then the structure
$\makeb(T,x,T')$ formed by attaching a left-pointing arrow from $x$ to
$T$ and a right-pointing arrow from $x$ to $T'$ is also in $\T$. See
Figure \ref{fig:searchtree}
\end{enumerate}

\begin{figure}[h]
\begin{center}
\input{figures/cp5F-searchtree.latex}
\end{center}
\caption{Creating a new search tree by applying rule 2}
\label{fig:searchtree}
\end{figure}


The number $x$ is called the \emph{root} of the tree that is formed.

\begin{problemparts}

\problempart Draw all the different search trees in $\T$ that have nodes
1, 2, 3, 4, 5.


\solution{
See Figure \ref{fig:possibilities}
%(1 2 (4 3 5)) and ((1 3 2) 4 5).

\begin{figure}[h]
\begin{center}
\input{figures/cp5F-st.latex}
\end{center}
\caption{The two possible search trees}
\label{fig:possibilities}
\end{figure}

}

\ppart
Define a function $\membern:\naturals \cross \T \to \set{0,1}$
recursively as follows:
\begin{eqnarray}
\membern(n,n)  & \eqdef & 1,\\
\membern(n,m)  & \eqdef & 0, \text{ for } n \neq m \in \naturals,\\
\membern(n,\makeb(T,n,T')) & \eqdef & 1,\\
\membern(n,\makeb(T,m,T')) & \eqdef & \membern(n,T)) \text{ for } n < m,\label{mn<}\\
\membern(n,\makeb(T,m,T')) & \eqdef & \membern(n,T')) \text{ for } n > m.
\end{eqnarray}

Prove that
\[
\membern(n,T) = 1 \iff n \in \nodes(T).
\]

\solution{
\begin{proof}
Note that we are asked to prove \emph{both} directions! ($\iff$). The
proof will be by structural induction on the definition of $\T$. 
\begin{description}
\item[Base Case:] $|T|=1$. The tree has only one node
representing a natural number $t$. 
\begin{description}
\item[($\Longleftarrow$)]If $n\in \nodes(T)$ then $n=t$ and so by rule
(1), $\membern(n,t)=1$.
\item[($\Longrightarrow$)]If $\membern(n,t)=1$ then, by rule (2), it is
impossible to have  $n\neq t$ because in that case
$\membern(n,t)=0$. Therefore, $n=t$ and so $n \in \nodes(T)$
\end{description}

\item[Induction Step:] There is only one operation to consider, namely $\makeb(T,x,T')$. Assume that
\begin{eqnarray*}
\membern(n,T) = 1 \iff n \in \nodes(T),\label{mnT}\\
\membern(n,T') = 1 \iff n \in \nodes(T')
\end{eqnarray*}
to prove
\begin{equation*}
\membern(n,\makeb(T,x,T')) = 1 \iff n \in \nodes(\makeb(T,x,T')).
\end{equation*}
\begin{description}
\item[Case 1: ($n = x$)] Then, by the definiton of ``nodes'' $n \in
\nodes(\makeb(T,x,T'))$. At the same time, $\membern(n,\makeb(T,x,T')) = 1$ by definition of
$\membern$. Notice that there is no if-then statement here. If $n=x$
then both sides of the double implication ($\iff$) have to be true.

\item[Case 2: ($n < x$)] Then $n \in \nodes(\makeb(T,x,T'))$ iff $n \in \nodes(T)
\union \nodes(T')$ by definition of $\nodes$.  But since $\makeb(T,x,T')
\in \T$, we know $x < \min(\nodes(T'))$, so $n \notin \nodes(T')$.
Therefore, $n \in \nodes(\makeb(T,x,T'))$ iff $n \in \nodes(T)$.
By~(\ref{mnT}), $n \in \nodes(T)$ iff $\membern(n,T) =1$.  But
$\membern(n,\makeb(T,x,T')) = \membern(n,T)$ by~(\ref{mn<}), completing
the proof.

\item[Case 3: ($n > x$)] Symmetric to Case 2.
\end{description}
\end{description}
\end{proof}
}

\end{problemparts}
\end{problem}
\fi
