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

%\backwardscompatibility        % !! use for backwards compatibility
%\showsolutions                 % !! use to force solutions & skip query
%\hidesolutions                 % !! use to force no solutions & skip query
\renewcommand{\coursecopyrightnames}{Prof.~Albert~R.~Meyer}

\def\bparts{\begin{problemparts}}
\def\eparts{\end{problemparts}}
\def\ppart{\problempart}
\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}}

\begin{document} 
\inclassproblems{5F}
\newcommand{\deriv}{\frac{d}{dx}}
\renewcommand{\paren}[1]{\left(#1\right)}

\newcommand{\setl}{\mathbb{L}}
\newcommand{\setlone}{\mathbb{\ell}_1}
\newcommand{\setltwo}{\mathbb{\ell}_2}
                    % !! start the paper

\begin{problem}
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, $\deriv \ide(x) = 1$ (constant) and so by rule \ref{const}, it is in
$\EF$. Similarly, $\deriv \cos(x) = -\sin(x)$ which is also in $\EF$
since $\sin(x)\in \EF$ by rule 3 and therefore $-\sin(x)$ as well (by
rule \ref{+-}). 

\item[Induction Case:] ($f^{-1}$).  Assume $df/dx \in \EF$ to prove
$\deriv f^{-1}(x) \in \EF$.  We know that $\deriv f^{-1}(x) =
1/(df/dx)$. Since $df/dx \in \EF$ (by assumption), so is $\frac{1}{df/dx}$ (by~\ref{+-}). 

\item[Induction Case:] ($f \compose g$).  Assume $df/dx, dg/dx \in \EF$
to prove $\deriv(f\compose g) \in \EF$. $\deriv(f\compose g)=\deriv
\paren{f(g)}=\frac{d}{dg}f(g)\cdot\frac{dg}{dx}$ which is in $\EF$  by~\ref{cmp}
and~\ref{+-}. The other cases are similar.
\end{description}
\end{proof}


}
\end{problem}

%%%%%%%%%%%%%%%%%%%%%%% PROBLEM %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%5


\begin{problem}

\bparts

\ppart Give a recursive definition of the set of $\leaves$ of a Rooted
Binary Tree.

\solution{
Let $T, t_1, t_2$ be trees and let $\setl, \setlone, \setltwo$ represent their
respective sets of leaves.  We can then define the set of leaves of a
Rooted Binary Tree $T$ as follows:

\[
\begin{array}{llll}
 \setl &\eqdef& \set{T}&\text{if $|T|=1$ (the sole vertex of the tree is the
 only element of the set of leaves)}\\
\setl &\eqdef& \setlone&\text{if $T=\makeleft(t_1)$ or
 $T=\makeright(t_1)$}\\
\setl &\eqdef& \setlone \cup \setltwo& \text{if $T=\makeb(t_1, t_2)$}
\end{array}
\]
}


Full Binary Trees 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}

%%%%%%%%%%%%%%%%%%%%%%% PROBLEM %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%5

\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}

\end{document}

%%%%%%%%%%%%%%%%%%%%%%%REMOVED PROBLEMS %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%5


%------------------------------------------------------------
% source: taken from fall 99pset 6, #4
% topic:game trees
%

\begin{problem}\label{game}
Consider the following game for two players.  The players alternate moves.
A move consists of a pair $(x,y)$ of natural numbers, subject to the
constraint that no move may be $\geq$ to any previous move in both
coordinates.  The player who makes the $(0,0)$ move is the loser.

Find a winning strategy for the first player.

\solution{
The first player has two winning strategies:

{\bf Strategy 1:} If the first player starts with $(1,1)$ then
whatever the second player picks, either $(0,n)$ or $(n,0)$ for some
$n$, the first player will respond with, respectively, $(n,0)$ or
$(0,n)$.  By symmetry, the first player will always have a valid move
whenever the second player had a move, except when the second player
picks $(0,0)$ and loses.


{\bf Strategy 2:} The second winning strategy is slightly more tricky:
The first player starts by picking $(2,0)$,\footnote{Of course,
picking $(0,2)$ would be equivalent, and the following argument will
hold for it as well, with x and y coordinates replaced} and then:
\begin{itemize}
\item
If the 2nd player picks $(0,n)$ for any $n\geq{1}$, 1st player responds with
$(1,n-1)$.
\item
If the 2nd player picks $(1,n)$ for any $n\geq{0}$, 1st player
responds with $(0,n+1)$.
\end{itemize}
And the above procedure should be repeated for all consecutive moves.
Notice that if player 2 had a valid move, so does player 1, unless
player 2 picked $(0,0)$ and lost.

Furthermore, there are no other winning strategies for player 1,
because if she starts with any other legal move, player 2 will be able
to adopt either of the two winning strategies and win for sure:
\begin{itemize}
\item
If player 1 picks some $(m,n)$ where $m,n\geq{1}$ and
$(m,n)\neq(1,1)$, then player 2 can pick $(1,1)$ next, and then use
the first strategy to win against player 1.
\item
If player 1 picks some $(0,n)$ or $(n,0)$ where $n\geq{3}$, then
player 2 can respectively pick $(0,2)$ or $(2,0)$ next, and then use
the second strategy to win against player 1.
\item
If player 1 picks $(1,0)$ or $(0,1)$ then player 2 picks the other one
and wins.
\end{itemize}
}

\end{problem}


\begin{problem}\label{strategy}

Many two-person games in which players alternate moves---like chess,
checkers, and tic-tac-toe---can be represented abstractly by \emph{game
trees}.

The root of a game tree has children labeled with each of the possible
initial moves by the first player.  For example, in the game tree for
tic-tac-toe, the root has nine children corresponding to the nine
boxes that the first player could mark with an~X.  Each of these
nodes has eight children corresponding to the eight remaining boxes
which the second player could mark with an~O, and so on.

In general, each node corresponds to a situation in the game, and its
children correspond to each of the possible moves by the player whose
turn it is in that situation.  The leaves of the tree correspond to
situations where no moves are possible---the game is over.  The leaves
are labelled with \emph{win}, \emph{lose}, or \emph{draw}, indicating
the outcome for the first player.  (A win for one player is a loss for
the other---no ``everybody wins''-type games at MIT. \texttt{:-)})

A \emph{strategy} for a player in a game specifies which move the player
should make in any situation where it is that player's turn to move.  A
\emph{winning} stategy ensures that the player will win no matter what
moves the other player makes.  Similarly, a \emph{non-losing} stategy
ensures that the player will \emph{win or draw} no matter what moves the
other player makes.

For example, most elementary school children figure out non-losing
strategies in tic-tac-toe for \emph{both} the first and second players.
There is no winning strategy in tic-tac-toe for either player.  No one
knows if any player has a winning strategy for chess or checkers.
However, on general principles, we can be sure that at least one player
has a non-losing strategy.

We want our games to terminate with a definite outcome---they cannot go on
forever.  These are called \emph{terminating games}.  For example, chess
and checkers are terminating games because of a rule that the game is a
draw if the same board position repeats too many times.

So game trees for terminating games are exactly the \emph{finite-path
trees} with leaves $\set{\emph{win}, \emph{lose}, or \emph{draw}}$.

Prove that for any two-person terminating game, at least one of the
players has a non-losing strategy.

\solution{
\begin{proof}
The proof is by structural induction on the game tree.
Let $P(T)$ be the proposition that for a game tree, $T$, at least one
of the players has a non-losing strategy.

{\bf Base case:}
For the base case of a single-node tree, the node is labeled \emph{win},
\emph{lose}, or \emph{draw}.  If the node is labeled \emph{win} or
\emph{draw}, then the first player has a non-losing strategy.  If
the node is labeled \emph{draw} or \emph{lose}, then the second
player has a non-losing strategy.  In both cases, there is a player with
a non-losing strategy.

{\bf Structural Induction Step:} In the inductive step, we want to prove
that for any game tree, $T$, if $P(T')$ holds for each immediate
subgame, $T'$, of $T$, then $P(T)$ holds.

So suppose $T$ is a game tree and there is a non-losing strategy for at
least one of the players for every immediate subgame, $T'$, of $T$.

Let $A$ be the player who moves first in the game defined by $T$, and
let $B$ be the player who moves second.  If player $B$ has a non-losing
strategy for \emph{every} subgame, $T'$, of $T$, then $B$ also has a
non-losing strategy for the full game tree $T$: no matter what move
player $A$ makes, player $B$ simply follows his non-losing strategy for
the immediate subgame determined by $A$'s move.

On the other hand, suppose there is some immediate subgame, $T_0$, of
$T$, for which player $B$ does not have a non-losing strategy.  
Since, by induction hypothesis, \emph{some} player has a non-losing
strategy for $T_0$, it must be player $A$ that the non-losing strategy
for this subgame.  But then player $A$ has a non-losing strategy for the
full game tree $T$: namely, make the move that leads to subgame $T_0$
and then pursue the non-losing strategy for that subgame.

In either case, at least one of the players has a non-losing strategy.
This completes the proof of the induction step, and thus the whole proof
by structural induction.

We conclude that $P(T)$ holds for all games trees, $T$.
\end{proof}
}

\end{problem}


\begin{problem}
We continue analyzing the game from Problem~\ref{game} to show that it has
a finite-path game tree---so we could in principle have concluded from
Problem~\ref{strategy} that there was some winning strategy, even without
the detailed solution to Problem~\ref{game}.

Namely, we will show that the game \emph{must} terminate, even if the two
players conspire to play as long as possible.

\medskip

At any point in the game, a valid move $(a,b)$ is said to be
\emph{bounded} iff both $a$ is bounded above by the $x$-coordinate of some
previous move and $b$ is bounded above by the $y$-coordinate of some
previous move.  Notice that there are only a finite number of bounded
moves at any point after the first move.

For example, if the previous moves have been $(1,3),(3,1), (2,2)$, then
there are ten possible bounded moves:
$\{(1,2),(2,1),(1,1),(0,3),(0,2),(0,1),(0,0),(1,0),(2,0),(3,0)\}$.  There
is also an infinite number of possible unbounded moves at this point,
namely, any move with one coordinate equal to $0$ and the other larger
than $3$.

\begin{problemparts}
\ppart  Is the number of bounded moves a weakly decreasing variable?
weakly increasing?  Explain.

\solution{Neither.

The number can increase if next move has larger $x$-coordinate but smaller
$y$-coordinate than any previous move.

The number will decrease if the next move is bounded.}

\eparts

For any state $S$ of the game after the first move, let $v(S)$ be the
sum of the minimum of the $x$-coordinate and minimum $y$-coordinate among
the previous moves, and let $b(S)$ be the number of possible
bounded moves.  Define the \emph{measure}, $M(S)$, of the state to be the
pair $(v(S), b(S))$.

Define $\prec$ to be the \emph{lexicographical} ordering on pairs of
natural numbers:
\[(m,k) < (m',k') \iff [(m < m') \lor (m = m' \land k < k')\]


\bparts
\problempart Prove that $\prec$ is a total order on $\naturals^2$ that is
not reflexive.

\ppart Prove that any nonempty subset of $\naturals^2$ has a $\prec$-least
element.  (Lexicographic order is a \emph{well-order}.)

\solution{Let $S$ be some nonempty subset of $\naturals^2$.  Let $S_x
\eqdef \set{m \suchthat \exists n\ (m,n)\in S}$.  Then by the Least Number
Principle there is a smallest element $x_{min}$ in $S_x$.  Similarly,
$y_{min}$ be the least element in the $\set{n \suchthat (x_min,n) \in S}$

Then $(x_{min},y_{min})$ is the $\prec$-least element in $S$.}

\problempart Show that $v$ is a weakly decreasing variable.

\problempart Show that the measure $M$ is a strictly $\prec$-decreasing
state variable.  Conclude that the game will terminate, even if the
players conspire to play as long as possible.

\solution{
We first show that the measure $M(S)=(v(S),b(S))$ decreases with every
move according to the ordering in $\naturals^2$ defined above.

Assume by contradiction that for some move $(a,b)$ leading from state $S$
to state $S'$, we have that $M(S')\geq{M(S)}$.  There are two cases

Case 1: $(a,b)$ is a bounded point.  Then the number of bounded moves in
$S'$ at least one less than in $S'$, and since $v$ is nondecreasing, we
conclude that $M(S') \prec M(S)$.

Case 2: $a >$ the maximum previous $x$-coordinate.  Since $(a,b)$ is a
valid move, $b$ must be less than the minimum previous $y$-coordinate.
So $v(S') < v(S)$ and therefore $M(S') \prec M(S)$.

Among the set of all states in a game, there must be a must be a
$\prec$-least state, since it is a well-order.  Since any move would
decrease the measure of this state, it must be a final state of the game.
}
\end{problemparts}
\end{problem}

%%%%%%%%%%%%%%%%%%%%%%% PROBLEM %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%5


\begin{problem} \textbf{Structural Induction}

The set $SSS$ of ``super-symmetric strings'' is defined as follows:
\begin{enumerate}
\item
The length one strings consisting of individual letters of the
alphabet, $a$, $b$, $c$, $d$, $\ldots$, $z$, are in $SSS$. 
\item
If $\alpha$ and $\alpha'$ are two strings in $SSS$ then the string
$\alpha \alpha' \alpha$ is in $SSS$.
\item
$SSS$ contains nothing else.
\end{enumerate}
\begin{problemparts}
\problempart
Which of the following are super-symmetric strings?
\begin{itemize}
\item[i.]  $a$
\item[ii.]  $aaaba$
\item[iii.] $abcbacabcba$
\item[iv.] $\lambda$, the empty string
\item[v.]. $abaabcbaaba$
\end{itemize}

\solution{
i. Yes.  This is stated in part 1 of the definition.

ii. No.  This string is not of the form $\alpha \alpha' \alpha$.

iii. Yes.  Formally, consider $\alpha'=aca$, $\alpha=bcb$.  Then we have
a string of the form $a \alpha \alpha' \alpha a$, which is in $SSS$
by parts 1 and 2 of the definition.

iv.  No.  By part 3 of the definition

v. Yes. Similar reasoning to part iii shows that the string $bcb$ is in
the middle of the super-symmetric string, with the string $a$ wrapped
around it, and with the string $aba$ wrapped around that.
}

\problempart Prove by structural induction that in any super-symmetric
string, exactly one letter appears an odd number of times.

%%%
%Fix this either to be more complete, or to use Structural Induction.
%Find out what structural induction is, too.
%%%

\solution{

\begin{proof}
 Define $P(e)$: String $e$ has exactly one letter which appears an odd number of times.
\begin{tabbing}
XXX\=XXX\=XXX\=XXX\=XXXXXXXXXXXXXXXXXXXXX\=    \kill
Prove: $\forall e \in SSS \ P(e)$.\\
1. (Base) $P(a)$\>\>\>\>The string $a$ has exactly one letter which appears an odd number of times.\\
2. (Base) $P(b)$\>\>\>\>Same for the string $b$\\
$\vdots$\\
26. (Base) $P(z)$\>\>\>\> Still has exactly one letter which appears once.\\
27. (Inductive Step) $\forall e, e' \in SSS \ P(e)\wedge P(e') \longrightarrow P(ee'e)$ \\
\>1. Fix $e,e' \in SSS$.\\
\>2. Assume $P(e) \wedge P(e')$.  That is, each of $e$ and $e'$ has exactly one letter which\\
\>\>appears and odd number of times.\\
\>3. By the inductive hypothesis, both $e$ and $e'$ have exactly one letter which appears an odd\\
\>\> number of times.  When we form the string $ee'e$, the letters in $e$ all get repeated, \\
\>\> and thus they all appear an even number of times.  By the IH, there is one letter in $e'$\\
\>\> which appears an odd number of times in $e'$.  Now, even if this letter is also present in\\
\>\>$e$, it will still appear an odd number of times in $ee'e$ (since
the sum of an odd number \\
\>\>and an even number is odd).  Therefore, we
have shown $P(ee'e)$.\\ 
\>4. QED.\\
\end{tabbing}
\end{proof}

}

\end{problemparts}
\end{problem}





