
\problem %balls in bins
Suppose that I throw 20 indistinguishable balls into 4
distinguishable bins.  What is the probability that no bin
gets exactly 5 balls in it?

\problem %sample tree 
Suppose you are playing the {\em Let's Make a Deal} game, but you
happen to know that Monty will always open door number 1 whenever he
has that choice (under the standard rules).  How should you play?
What are your chances of winning?

\problem The Sock Drawer.
A drawer contains red socks and black socks.  When two socks are drawn at 
random, the probability that both socks are red is $\frac{1}{2}$.  How small 
can the number of socks in the drawer be?


\problem You are blindfolded and randomly choose fruit out of a fruit
basket with 5 pears, 3 apples and 2 oranges, what is the probability
that you

\begin{problemparts}
\ppart
pick out an apple on the first pick?  

\ppart
pick out an apple and an orange on the first 2 picks?

\ppart
pick out an apple followed by an orange on the first 2 picks?

\ppart
pick out an orange followed by an apple on the first two picks?

\ppart
pick out 3 pears before picking out an apple (ie,  keep on picking until
you have 3 pears)  
\end{problemparts}

\problem The Flippant Juror.
A three man jury has two members  each of whom independently has probability 
$p$ of making the correct decision and a third member who flips a coin for each
decision (majority rules).  A one-man jury has probability $p$ of making the 
correct decision.  Which jury has better probability of making the correct
decision?

\problem Family Matters
Assume that the probability a child is a boy is $0.51$ and that the sexes
of children born into a family are independent.  What is the probability 
that a family of five children has
\bparts
\ppart exactly three boys?
\ppart at least one boy?
\ppart at least one girl?
\ppart all children of the same sex?
\eparts

\problem How many different strings with five or more characters can be made 
from the letters in {\it RESTLESS}?

\problem
How many ways can 4 coins be placed in 3 pouches if 
\begin{problemparts}
\problempart both the coins and the pouches are distinguishable;
\problempart the coins are distinguishable but the pouches are not;
\problempart the pouches are distinguishable but the coins are not;
\problempart neither the coins nor the pouches are distinguishable.
\end{problemparts}



Given a weighted pair of dice each with the following probabilities: \\
1:  $\frac{1}{12}$ \\
2:  $\frac{1}{24}$ \\
3:  $\frac{1}{8}$ \\
4:  $\frac{5}{24}$ \\
5:  $\frac{3}{8}$ \\
6:  $\frac{1}{6}$ \\
What is the probability of getting 
a sum of two on the dice? a sum of seven on the dice? a sum of eleven on 
the dice?

\problem

Suppose five points are chosen inside a square of side length 1.  Prove
that there is at least one pair of points whose distance is at most
$\frac{1}{\sqrt{2}}$.

Hint: divide the square into subsquares.

\problem Give a counterexample to the following claim and then explain
why the proof is wrong.

Claim: if every horse in a herd is the same color as some other horse
in the herd, then all horses in the herd are the same color.

Proof: Induction on the number of horses.  Base case of 2 horses
trivial: under the hypothesis, one must be the same color as the
other.  So consider a set of $n$ horses satisfying the criteria, and
suppose we add an $(n+1)^{st}$ horse.  By assumption, this horse is
the same color as some other horse.  By inductive hypothesis, that
horse is the same color as all the other horses.  So all the horses
including the $(n+1)^{st}$ are the same color.

\problem  The Stuff

It's late at night and you and some of your friends are discussing
``The Stuff,'' a really bad movie shown at the last LSC Sci-Fi
Marathon.  In the movie, people who eat a dessert substitute called
``The Stuff'' (which is really an alien entity from the center of the
earth) become addicted to the substance, eating more and more of it
forever.  In particular,
\begin{itemize}
\item On day $0$, one person was addicted.
\item On the first day that a person is addicted they eat one carton of the 
stuff, and on any other day they eat $s$ times as many cartons as they ate
the day before.
\item Each day, $p$ new people are addicted.
\end{itemize}

\begin{problemparts}
\problempart
Find a recurrence for how much of ``The Stuff'' is eaten on day $n$ if
(Don't forget to specify a base case.)

\ppart Use plug and chug to solve the recurrence as a summation.

\ppart Give a closed form for the summation.

\end{problemparts}



\problem Prove that for any two positive increasing functions $f$ and
$g$, 
\[
\max (f(n),g(n)) = \Theta(f(n)+g(n))
\]


\problem Recall that a {\em tournament graph} $G$ is a directed graph
in which, for every vertex pair $u \ne v$, exactly one of the edges
$(u,v)$ and $(v,u)$ is in $G$.  An {\em apex} of the tournament is a
vertex $a$ such, for every other vertex $v$, either $(a,v)$ is an edge
or, for some $w$, both $(a,w)$ and $(w,v)$ are edges.  In other words,
either $a$ beats $v$, or $a$ beats someone who beats $v$.  Prove by
induction on the number of vertices that any tournament has an apex.


\problem
Let $D_n$ be the determinant of the $n\times n$
tri-diagonal matrix
\[\left[\begin{array}{ccccc}
  a & b &   & &\\
  c & a & b & &\\
    & c & \ddots & \ddots & \\
    &   & \ddots & \ddots & b \\
    &   & & c & a 
  \end{array} 
  \right]
\]
where $a=b+c$, and assume $b\neq c$.
\bparts
\ppart
 Show that $D_n$ satisfies the linear recurrence
 $D_n = aD_{n-1} - bc\cdot D_{n-2}$.
\ppart
 Find the general solution to the above recurrence
\ppart
 Use the initial conditions for $D_1$ and $D_2$
 to find an explicit formula for $D_n$
\eparts


%an infinity review
\problem
Use a diagonalization argument to show that the set of functions from
the positive integers to the set $\{0, 1, 2, 3, 4, 5, 6, 7, 8, 9\}$ is
uncountable. (Problem 30, Sec. 1.7 of Rosen)

\problem You start working for a company that pays you a starting
salary of $1$ dollar in year 0, and gives you a raise of $r$ percent
at the beginning of each year thereafter.
They put you on a retirement plan with the following property: at the
end of each year, they add to the account:
\begin{itemize}
\item A fraction $f$ of your just-ended year's salary
\item interest of $p$ percent on what was already in the account that
  year.
\end{itemize}
So at the end of year 0, they put $f$ dollars into the account (which
is empty so it earns no interest), and raise your salary to $(1+r)f$.

\begin{problemparts}

  \ppart How much money (from your salary) does the company add into
  your retirement account in year $n$?

  \ppart Let $m(n)$ be the amount of money in your retirement account
  at the beginning of year $n$.  Give a recurrence for $m(n)$ (note
  that $m(0)=0$, while $m(1)=f$).

  \ppart Plug and chug to solve the recurrence so as to express $m(n)$
  as a sum. 

  \ppart Find a closed form for the sum.  Assume that $p \ne r$.

\end{problemparts}


\problem Solve the recurrence $T(n)=2T(n/2)+\log n$ by applying the
substitution $n=2^m$.  Give asymptotic ($\Theta$) bounds in terms of
$n$.

Each of your friends has come up with a recurrence too.  Solve each of them.
\begin{problemparts}
\problempart

$T(n) = a T(\frac{n}{2}) + n^2 $ and $T(1)=3$

\problempart
$T(n) = 3 T(n-1) + 4 T(n-2) $, $T(1) = 1$, and $T(2) = 2$

\problempart
$T(n) = 3 T(n-1) + 4 T(n-2) +n $, $T(1) = 1$, and $T(2) = 2$

\problempart

$T(n) = T(\log n) +n \log n$ and $T(1) = 1$

\end{problemparts}


\problem
\begin{enumerate}

\item
Obtain a general solution to the difference equation \\

\begin{displaymath}
f(n) = 7f(n-2)+6f(n-3) + 8^n
\end{displaymath}

You are given that the roots to the characteristic polynomial of this equation are $3,-1$, and $-2$.

\item
Obtain asymptotic bounds for the recurrence relation
\begin{displaymath}
T(n) = \frac{16}{9}T(\frac{n}{2}+n^{1/3})+5T(\frac{n}{3})
\end{displaymath}

\end{enumerate}

%hard
\problem 
Show by induction

\begin{displaymath}
\sum_{k=1}^{m+1} {m+1 \choose k} \frac{(-1)^{k+1}}{k+1} = \frac{m+1}{m+2}
\end{displaymath}

{\it Hint: manupulate the expression
$ (1+x)^{m+1} = \sum_{k=0}^{m+1} {m+1 \choose k} x^k $ }

\problem
Obtain an exact solution to the recurrence relation which is defined for all powers of $3$.

\begin{displaymath}
x(n) = 4x(\frac{n}{3})-4x(\frac{n}{9})+ln(n) \\
\end{displaymath}

subject to the initial conditions $x(1) = 0 , x(3) = ln3$. \\
You are also given that a particular solution to this equation (a solution that satisfies the equation but not the initial conditions) is \\
$x_p(n) = ln(n) + 4ln3$

\problem % summations and asympthotic notation
In this problem you must find an asymptotic bound 
to the function
\[f(n) = \sum_{k=1}^{n}{k^2+k+1\over 2k-1}.\]
\bparts
 \ppart
   Show that ${k^2+k+1\over 2k-1}$ is 
   $\Theta(p(n))$ for some polynomial $p(n)$.
 \ppart
   Use the integral method to find asymptotic tight bound 
   to the summation $\sum_{k=1}^n p(k)$, i.e., find a function 
   $g(n)$ such that $\sum_{k=1}^n p(k)$ is $\Theta(g(n))$.
 \ppart
   Deduce from part $(a)$ and part $(b)$ an asymptotic 
   tight bound to the function $f(n)$. 
   {\bf (prove / do not prove?)} 
\eparts

%some summations
\problem 

Give asymptotically tight bounds on the following summations.  Assume that
$r \geq 0$ and $s \geq 0$ are constants.

\bparts

\ppart $\sum_{k=1}^{n} k^r$
\ppart $\sum_{k=1}^{n} \log^s k$
\ppart $\sum_{k=1}^{n} k^r \log^s k$
\eparts

\problem How many 10-bit strings contain either 5 consecutive 0s or 5
consecutive 1s?


\problem
How many positive integers less than 720 are divisible by 6 and 9 but not
by 8 and not by 20?  How many are divisible by either 6 or 9 (possibly
both) but still not by 8 and still not by 20?  How many are there in
each of the above that also aren't divisible by 25?  Justify your answer.


How many ways can 4 coins be placed in 3 pouches if 
\begin{problemparts}
\problempart both the coins and the pouches are distinguishable;
\problempart the coins are distinguishable but the pouches are not;
\problempart the pouches are distinguishable but the coins are not;
\problempart neither the coins nor the pouches are distinguishable.
\end{problemparts}


\problem
Let $A$ be a set containing $a$ distinguishable vertices
and $B$ be a set containing $b$ distinguishable vertices different
from those in $A$.
How many bipartite graphs are there with parts $A$ and $B$?
A (partial) matching is a subgraph of a given graph that has no vertices
with degree greater than one.  (Thus the edges match up pairs of vertices).
A maximal matching is a matching to which no edges of the original graph
can be added without creating a vertex of degree greater than one.
Let $K_{a,b}$ be the (bipartite) graph containing edges between every
vertex in $A$ and every vertex in $B$.  What can be said about the
number of edges in a maximal matching in $B$?  How many maximal matchings
are there in $B$ in the case $a = b = n$?  What about in the general case?

 
\problem
Give a formula for the coefficient of $x^k$ in the expansion of 
$(x+1/x)^{100}$, where $k$ ia an integer. 

\problem
A complete binary tree can be defined recursively as either a leaf node
or a non-leaf node with left and right children that are
complete binary trees that are {\em identical} to each other.
Prove that the number of leaves in a complete binary tree is a power of 2.
Define $E(l)$ to be the number of edges in a complete binary tree with $l$
leaves.  Give a recurrence relation for $E(l)$.  Solve the recurrence as shown
in recitation.  What is the total number of nodes in a complete binary
tree with $l$ leaves?  (Justify your answer).

\problem A {\em cut} in a graph is a partition of the graph vertices
into two groups.  An edge {\em crosses} the cut if it has one endpoint
in each group.  Prove by induction on the number of vertices that any
graph has a cut with at least half the graph edges crossing it.


\problem 

Let $F$ be the set of positive real functions 
and let $R$ be the relation on $F$ defined by 
$(f,g)\in R$ if and only if $f$ is $\Theta(g)$.
\bparts
 \ppart
   Prove that $\Theta$ is an equivalence relation.
 \ppart
   Let $H$ be the set of equivalence classes of $F$
   modulo $R$ and let $P$ be the relation on $H$ 
   defined by 
   \[ [f]P[g] \Longleftrightarrow f \mbox{ is } O(g). \]

   Show that the relation $P$ is well defined, i.e., 
   prove that if $fRf'$ and $gRg'$, then 
   $f$ is $O(g)$ if and only if $f'$ is $O(g')$.

 \ppart
   Prove that $P$ is a partial order on $H$.
\eparts

\problem Suppose we are given a tree $T$.  {\em Rooting $T$ at vertex
  $v$} means assigning a direction to every edge of $T$ (that is,
replacing every undirected edge with a directed one) such that $v$ has
outdegree 0 and every other vertex has outdegree 1.  The unique
``outneighbor'' of a vertex $u$ (that is, the vertex $w$ for which
there is a directed edge $(u,w)$) is called the {\em parent} of $u$;
the other ``inneigbors'' of $u$ are called the {\em children} of $u$.
  
\bparts
\ppart 
Prove by induction on the number of vertices that any tree can be
rooted at any of its vertices
\ppart
Extend your proof to show that the path defined from any
vertex by repeatedly following the unique parent edges eventually
reaches the root.
\eparts

\problem Prove that
$ \sum_{k=1}^{n-1} \frac{1}{k(k+1)} = 1 - \frac {1}{n}$

\problem Let $G=(N,E)$ be a simple graph, i.e., an undirected graph
with no self-loops.  A subset of nodes $S\subseteq N$ is an {\em
  independent set} if no two nodes in the set are adjacent (connected
by an edge).  Prove by induction on the number of vertices that any
graph with maximum degree $\Delta$ has an independent set of size at
least $n/(\Delta+1)$.


\problem
Discover and prove a formula for
$$
\sum_{k=0}^n k^3 {n \choose k}
$$

\problem algorithm for constructing a spanning forest by deleting
every edge on a cycle.  prove correctness.

 \problem A {\em Tournament Graph} is a directed graph such that if
 $u$ and $v$ are vertices then either $(u,v)$ is an edge or $(v,u)$ is
 an edge but not both. A {\em Directed Hamiltonian Path} is a simple
 path in a directed graph that contains every vertex exactly once. 
 Prove by induction on the number of vertices that every tournament
 graph has a directed Hamiltonian path.

\problem How many edges do each of the following graphs have?  For
which values of $n$ do the following graphs have an Euler circuit?
\bparts
\ppart $K_n$
\ppart $C_n$
\ppart $W_n$
\ppart $Q_n$
\eparts

\problem 
A {\em root} of a directed graph is a node $r$ from which 
any node in the graph can be reached.
A directed graph is {quasi-strongly connected} 
if for any pair of nodes $x$ and $y$ there exists 
a node $z$ from which $x$ as well as $y$ may 
be reached.

\begin{problemparts}
 \ppart Prove by induction on the number of nodes that
  for any finite directed graph $G$
  \[ G \mbox{ is quasi-strongly connected } \Longleftrightarrow
     G \mbox{ has a root}\]

 \ppart Show that the previous statement does not 
  necessarily hold if the graph is infinite.
\end{problemparts}

%POSETS

\problem Let $n$ be any integer, and let $S$ denote the set of all equivalence 
classes of the naturals mod $n$. Define a relation $R$ on $S$ by 
$[a]R[b]$ if the least element of $[a]$ is less than the least element 
of $[b]$.
Is $R$ a partial ordering?  Is it a total ordering?

\problem Show that a poset can be partitioned into $k$ chains, where $k$ 
is the largest number of elements in an antichain in this poset.

\problemopt
Let $p$ be a prime.  Define a relation $R \subseteq \{1,\ldots,p-1\}
\times \{1,\ldots,p-1\}  $ by 
$aRb$ if $ab = 1 \pmod{p}$.

\bparts
\ppart Prove that $R$ is a symmetric relation.
\ppart Prove that $R$ is a bijection.
\ppart What is $R^{-1}$?
\ppart Show that if $p$ is not prime, $R$ might not be a function.
\ppart Prove that $R$ is a symmetric relation.
\ppart Suppose $0 \le a<p$ but $p \mid a$.  What is $a$?
\ppart Suppose that $0 \le a < p$ and $ab=ac \pmod{p}$.  Prove $b=c \pmod{p}$.
\ppart Prove that $R$ is a function.
\ppart Prove that $R$ is injective.
\ppart Prove that $R$ is surjective.
\eparts


\problemopt

Consider the following definitions, based on the Peano-axiomatic
successor function $n \rightarrow n'$.
\begin{itemize}
\item $0$ is even.
\item $n'$ is odd if $n$ is even.
\item $n'$ is even if $n$ is odd.
\end{itemize}

Also recall the recursive definition of plus:
\begin{itemize}
\item $n+0 = n$
\item $n+k' = (n+k)'$
\end{itemize}

Prove (using only these definitions and the Peano Axioms) that the sum
of two odd numbers is even.


You are given a large chocolate bar which you wish to share among your
friends.  The bar is an $m \times k$ grid of smaller squares.  You can
break a piece on any grid line.  What is the minimum number of breaks
you can make to split the bar into n pieces?  Prove your answer. (A
break is a break in one piece, if you break two pieces at one time,
that's two breaks.)

\problem
Define a relation $R$ on $2^{\naturals}$
by the rule $(A,B) \in R$ if $A \cap B \ne \emptyset$.
%Decide whether this relation is reflexive, symmetric, antisymmetric, transitive.
Now let $f: \naturals \rightarrow S$ be a function to a certain set
$S$.  Define the relation $R_f$ on $2^{\naturals}$ by the rule $(A,B) \in
R_f$ if $f(A) \cap f(B) \ne \emptyset$.  

\long\def\comment#1{}

\begin{problemparts}
\comment{
\problempart Let $W=\{8,9,10\}$, $X=\{1,2,3\}$,
$Y=\{4,5,6\}$, and $Z=\{1,3,5\}$.  Show which pairs from $X,Y,Z$ are
related under $R$.  
\problempart Suppose $f(x)=\lfloor x/2\rfloor$.  Show which pairs of
$W,X,Y,Z$ are related under $R_f$.
\problempart Show whether $R$ is reflexive, symmetric, antisymmetric,
and/or transitive. 
}
\problempart Show that $R \cap R_f = R$
\problempart Now suppose that $f$ is injective.  Show that $R \cap R_f = R_f$
\end{problemparts}

\problem Let $R$ be a transitive relation, and define the relation $S$
by $a \tilde_S b$ if $a=b$ or if $(a,b)\in R$ and $(b,a)\in R$.  Prove
that $S$ is an equvalence relation.  Define a relation $T$ on the
equivalence classes of $S$ by $X \tilde_T Y$ if either $X=Y$ or, for
some $a \in X$ and $b\in Y$, $a \tilde_R b$.  Prove that $T$ is a
poset.


\problem

Let $F$ be a function from $A$ to $B$ and let $G=F^{-1}$ be its
inverse ($G$ is a relation from $B$ to $A$, but not necessarily a
function).
\begin{problemparts}
 \ppart Prove that $G\circ F$ is an equivalence relation over $A$.
 \ppart Is also $F\circ G$ an equivalence relation? 
  Justify your answer.
 \ppart Give necessary and sufficient contitions on $F$ 
  to make $F\circ G$ an equivalence relation.
\end{problemparts}


\problem

Consider the recursive definition of binary tree.
Prove that the set of binary trees is countable.

Now consider the following definition of (general) trees:
\begin{itemize}
 \item A single node is a tree.
 \item For any $n\geq 1$ a node with an ordered sequence of $n$
   {\em subtrees}, each of which is a tree.
\end{itemize}
Is the set of all trees also countable?
Justify your answer.

\problem  Let $\cal A$ be a set of pairwise disjoint sets.
Let $\cal B$ also be a set of pairwise disjoint sets.
Suppose there is a bijection $f:\cal A \rightarrow \cal B$
such that $f(A)$ and $A$ have the same cardinality $\forall A \in \cal A$.
Prove that $\bigcup_{A \in \cal A} A$ has the same cardinality as
$\bigcup_{B \in \cal B} B$.


\problem prove the composition of two bijections is a bijection.

\problem  
\bparts
\ppart Show that for any function $f: A \rightarrow B$, $|f(A)| \leq |A|$
\ppart Show that if there is a surjection $f: A \rightarrow B$ and a surjection
$g: B \rightarrow A$, then there is a bijection from $A$ to $B$.
\ppart Show that if there is a surjection $f: A \rightarrow B$ and an injection
$h: A \rightarrow B$, then there is a bijection from $A$ to $B$
\eparts

\problem
Decide whether the following functions from $\integers$ into $\integers$ are
injections.
 
\bparts
\ppart $f(n) = n-1$
\ppart $f(n) = n^3$
\ppart $f(n) = n^2+1$
\ppart $f(n) = \lceil n/2 \rceil$
\eparts

handouts/
\problem Let $z^R$ denote the (digit by digit) reversal of a base 10
number $z$.  Thus for example $356^R=653$.  Also $1200^R=21$ (since
leading zeros are ignored).  The following code reverses the digits of
a base 10 number.  (If $x=10q + r$, $x$ div $10 = q$ and $x$ mod $10 =
r$).
\begin{tabbing}
else \= else \= else \= else \=\kill
Reverse$(n)$\\
 \\
 $x=n$\\
 $y=0$\\
 while $(x>0)$\\
\>   $y = 10*y + (x \bmod 10)$\\
\>   $x = (x$ div $10)$\\
 return$(y)$\\
\end{tabbing}

Show correctness.


\problem Prove by induction that no two Fibonnacci numbers other than
the second and third are equal (hint: you may want to prove a
different statement that implies this one).

\problem
State the following arguments as  predicate logic 
formulae.  Prove or disprove.

\begin{problemparts}
\problempart
All elves are green.  Some elves have pointed ears.  Thus, some mythical
creatures that have pointed ears are not green.

\problempart
Find another

\end{problemparts}

\bigskip

%\newpage

\problem % Equivalence relations and mod, Daniele.

For any integer $n>1$ let $\approx_n$ be the equivalence 
relation $a \approx_n b$ if and only if $n|(a-b)$.
Answer the following questions:
\begin{itemize}
 \item Is $\approx_3\circ \approx_5$ an equivalence relation?
 \item Is $\approx_3\circ \approx 6$ an equivalence relation?
 \item For which $n$ and $m$ is $\approx_n\circ\approx_m$ 
  an equivalence relation? 
\end{itemize}
Give proofs or counterexamples to justify your ansewrs.

\bigskip

%\newpage

\problem
Remember the definition of inverse, complement and composition of 
(binary) relations:
\begin{eqnarray*}
 R^{-1} & = & \{(a,b) \colon (b,a)\in R\} \\  
 R^c & = & \{(a,b)\colon (a,b)\not\in R\} \\
 S\circ R = \{(a,b) \colon \exists c. (a,c)\in R \wedge (c,b)\in S\} \\
\end{eqnarray*}

Prove that for any relations $P,Y,Q,X$ we have 
\[ P^{-1}\circ Y \circ Q^{-1} \subseteq X 
   \Leftrightarrow
   P\circ X^c \circ Q \subseteq  Y^c.
\]



%\newpage


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%4

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%4

        \problem {Correctness, Recursive, Medium} \\
        Recall that a binary search tree is a binary tree where each node has a value 
        (we will assume each
        node has a distinct value), and which is governed by the following rules: \\
        For all nodes,
        \begin{itemize}
        \item
        If a node has a left child then the $value(node) > value(LeftChild)$.
        \item
        If a node has a right child then the $value(RightChild) > value(node)$
        \end{itemize}

        Prove that the following algorithm prints out all the values in a binary search
        tree in increasing order.

        \begin{verbatim}
        traverse(node)
          if (node has a LeftChild)
            traverse(LeftChild)
          print(node's value)
          if (node has a RightChild)
            traverse(Rightchild)
        \end{verbatim}
\bigskip



\newpage

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem
 We define a well-balanced string of parentheses to be:

\begin{itemize}

\item The empty string, $\epsilon$.

\item The string (V)W, where V and W are well-balanced strings of
parentheses.

\end{itemize}

The following procedure is designed to take an input that is a string
consisting only of left and right parentheses.
If its input is a well-balanced string of parentheses, it is meant
to return $\epsilon$.
If its input is a string of the form P)W, where P is a
well-balanced string of parentheses and W is an arbitrary
(possibly empty) string, then it is meant to return the string )W.
For any other input, it is meant to return the special value {\em error}.
It uses the auxiliary procedures First-char and Remove-first-char, which
return the first character of a string and everything but the first
character
of a string, respectively.  (The strings are presumed to be non-empty in
both cases).

\begin{tabbing}

Check($w$) \\
\ \ \ \= if ($w = \epsilon$) return($\epsilon$) \\
      \> while (First-char($w$) = ``(") \\
      \> \ \ \ \= $w \leftarrow \mbox{Remove-first-char}(w)$ \\
      \>       \> $w \leftarrow \mbox{Check}(w)$ \\
      \>       \> if (($w = \epsilon$) or ($w = ${\em \ error})) \\
      \>       \> \ \ \ \= return({\em error}) \\
      \>       \> else \\
      \>       \>       \> $w \leftarrow \mbox{Remove-first-char}(w)$ \\
      \> return($w$) \\
\\
\end{tabbing}


If the procedure is correct, prove that it is correct.
If the procedure is incorrect, explain why it is incorrect,
demonstrate how it fails on a specific input,
fix it (staying as faithful as possible to the given procedure),
and prove that your revised version is correct.
You should only consider inputs which consist entirely
of left and right parentheses.
NO PARTIAL CREDIT WILL BE GIVEN FOR PROVIDING OR PROVING CORRECTNESS
OF A DIFFERENT PROCEDURE WITHOUT SOLID JUSTIFICATION THAT THE PROCEDURE
ABOVE IS INCORRECT.

\bigskip



\newpage

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem
  Let $A$ be an infinite sequence of real numbers such that
$$A_n \leq A_{n+2} \ \forall n \in \naturals \mbox{and}$$
$$A_n \leq A_{n+3} \ \forall n \in \naturals.$$
The search problem in $A$ is defined as follows.  Given a
real number $r$ and natural numbers $i, j$, find an index $m$ such
that $i \leq m \leq j$ and $A_m = r$.
The following algorithm is supposed to solve the search problem if
possible and return the special value {\em missing} otherwise.


\begin{tabbing}

Find($r$, $i$, $j$) \\
\ \ \ \= if ($j - i < 5$) \\
      \> \ \ \ \= $l \leftarrow i$ \\
      \>       \> while (($l \leq j$) and ($A_l \not = r$)) \\
      \>       \> \ \ \ \= $l \leftarrow l + 1$ \\
      \>       \> if ($l \leq j$) \\
      \>       \>       \> return($l$) \\
      \>       \> else \\
      \>       \>       \> return({\em missing}) \\
      \> else \\
      \>       \> $k \leftarrow \lfloor \frac{i + j}{2} \rfloor$ \\
      \>       \> if ($A_k > r$) \\
      \>       \>       \> return Find($r$, $i$, $k + 1$) \\
      \>       \> else \\
      \>       \>       \> return Find($r$, $k - 1$, $j$) \\
\end{tabbing}

If the algorithm is correct, prove that it is correct.
If the algorithm is incorrect, explain why it is incorrect,
demonstrate how it fails on a specific input,
fix it (staying as faithful as possible to the given algorithm),
and prove that your revised version is correct.
NO PARTIAL CREDIT WILL BE GIVEN FOR PROVIDING OR PROVING CORRECTNESS
OF A DIFFERENT ALGORITHM WITHOUT SOLID JUSTIFICATION THAT THE ALGORITHM
ABOVE IS INCORRECT. \\
\\

\bigskip



\newpage



Peano Define odd and even.  prove sum of two odd numbers is even.

prove by induction that no two fibonacci numbers are equal.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%1
\problem
Prove or disprove\\
\begin{displaymath} 
\forall n \in \naturals,  \sum_{i=0}^{n} i^{2} = \frac{n(n+1)(2n+1)}{6}
\end{displaymath}

Prove (using formal definition of cardinality) that if $A \cap
B=\emptyset$, then $|A \cup B|=|A|+|B|$.


1. Write an iterative procedure for a binary search of a sorted list;
have them prove it finds the item if present.

2. Prove that the following routine, when called on inputs a and b,
returns the quotient and remainder on division of a by b.

Divide(a,b)

If (a<b)
   return (0,a)
else
   (q,r) <---- divide(a-b,b)
   return (q+1,r)

3. Joe is at point (1,0) on the coordinate plane and wants to walk to
his house at the origin.  Unfortunately, it is very windy: each time
joe moves 1 unit north or south, he is also blown one unit east or west;
each time he moves one unit east or west, he is also blown one unit
north or south.  

Give a state machine that describes Joe's motion.

Prove joe will never get home.

4. Consider the following algorithm:

Start with an array A indexed from 1 to n
For each i, set A[i] = i
Set A[1]=0
For i=2 to n
   if (A[i] not-equal 0)
      For each j \le n such that i | j
         set A[j] = 0
   
Prove that when this procedure terminates, the nonzero entries of A
will be precisely the prime numbers between 1 and n

\problem Give a set-theoretic definition of ordered pairs.  That is,
find a way to use a set $S(a,b)$ to represent the ordered pair
$(a,b)$.  The representation should have the property that
$S(a,b)=S(c,d)$ if and only if $a=c$ and $b=d$, and should work even
if $a,b,c,d$ are themselves sets.

\problem
Recall from Tutorial 1 that a group $G$ is a set closed under an 
operation $\cdot : G \times G \rightarrow G$ which is associative and such that
there exists an identity and each element has an inverse.

We say that the elements $a,b \in G$ are {\em congruent} if there exists
$g \in G$ such that $a = g \cdot b \cdot g^{-1}$.

Show that congruence is an equivalence relation.

\problem (Rosen 1.5-2) Suppose that $A$ is the set of sophomores at
MIT and $B$ is the set of students taking 6.042.  Express each of the
following in terms of set operations involving $A$ and $B$.
\begin{problemparts}
\problempart The set of MIT sophomores taking 6.042
\problempart The set if MIT sophomores not taking 6.042
\problempart The set of MIT students who are sophomores or are taking
6.042
\problempart The set of MIT students who either are not sophomores or
are not taking 6.042.
\end{problemparts}

\problem

A blindfolded man has a heap of 10 grey socks and 10 brown socks in a
drawer. How many must he select in order to to guarantee that there is
a matching pair?  How many must he select in order to guarantee a grey
pair? Answer the above questions by using the pigeonhole principle and
tell us what are the holes and what are the pigeons.

\problem Ordered pairs can be defined as a special kind of set.  Define the
ordered pair $(x,y)$ to be the set $\{x,\{x,y\}\}$.  Prove that
$(x,y)=(z,y)$ if an only if $x=z$ and $y=w$.  Be careful, since
$x,y,z,w$ might themselves be sets.

\problem 
Prove that for any relations $Q,R$ and $S$
\[ (Q \circ R) \cap S \subseteq 
   (Q \cap (S\circ R^T)) \circ (R\cap (Q^T\circ S)).\]

\problem  The inputs to the following procedure are natural numbers.
What does it compute?  Prove it.  Be sure to prove that it terminates.

\begin{tabbing}
foo($m$, $n$) \\
\ \ \ \= if ($m = 0$) return($n^2$) \\
      \> if ($n = 0$) return($m^2$) \\
      \> if ($m < n$) return($2n + 1 + \mbox{foo}(n - 1, m - 1)$) \\
      \> return($2m + 1 + \mbox{foo}(m - 1, n - 1)$) \\
\end{tabbing}

\problem A function $f$ is {\em unimodal} if it increases for a while
and then decreases (think of an upside down parabola).  That is, for
some $k$ (the {\em maximum} of the function) $f(1) < f(2) < \cdots <
f(k)$ and $f(k) > f(k+1) > \cdots > f(n)$.  Consider the following
algorithm to find the maximum of a function.  Prove that the algorithm
is correct.  Assume $n>2$.

\begin{tabbing}
else \= else \= else \= else \= \kill
FindMax$(f,n)$\\
    \> $l = 1$\\
    \> $h=n$\\
    \> while $(h-l \ge 3)$\\
    \>    \> choose 2 numbers $m_l$ and $m_h$ with $l < m_l < m_h < h$\\
    \>    \> if $(f(m_l) > f(m_h))$\\
    \>    \>    \> $h=m_h$\\
    \>    \> else\\
    \>    \>    \> $l=m_l$\\
    \> return $\max(f(l),f(l+1),f(l+2))$
\end{tabbing}


\problem (optional).  For the unimodal maximum finder, give a rule for
choosing $m_l$ and $m_h$ that will make the algorithm fast.  How many
comparisons will your algorithm perform, given your choice?

\problem 
{\bf (Optional?)}
Prove that the equation $R\circ X = S$ is solvable 
in $X$ if and only if
$S \subseteq R\circ (R^T\circ S^c)^c$.


\problem 
A stack is a data structure which is FILO (first in, last out).  Data
is added to the top of the stack, and also removed from the top of the stack.
A stack has three operations:
\begin{itemize}
\item {\em n=Pop(stack)} Returns the top item on the stack.  If there is
no item, returns an error.
\item {\em Push(stack,n)} Puts $n$ on the top of the stack
\item {\em Empty()} Returns TRUE if the stack is empty, FALSE otherwise.
\end{itemize}

Assume that the stack has infinite memory, and starts out empty.

\begin{problemparts}
\problempart
Show a state machine for these operations
\problempart
Prove that the only way to get an error is to execute more Pops than Pushes.
\problempart
Prove that after executing the following code, $q = x$.
\begin{verbatim}
   Push(stack, x) 
   q=Pop(stack) 
\end{verbatim}

\end{problemparts}

Problem 2:

Card shark problem: Deal $21$ cards into 3 columns row by row with the
faces up.  Allow your adversary to pick a card mentally without
telling which one it is but telling you in what column it resides.
Next "shuffle" the cards by stacking the cards in each column while
maintaining their order. (Note: The top card in the column would be at
top of the stack.)  You now have 3 stacks of 7 cards corresponding to
the 3 columns. Stack the three stacks of cards by placing the stack of
cards with the chosen card at the bottom.  Redeal the cards as before
and ask your adversary in what column is the card he chose at the
begining. Next, "shufle" again as described above.

What is the least number of times that you have to repeat the process
before you can identify the card your opponent has chosen?

Write a state machine, prove that there is a finite number of
repetions necessary for you to identify the chosen card using this
algorithm and prove that you'll always find the chosen card.


e.  Set up a correspondence between the natural numbers and a subset of
$\cal C$ such that every natural number corresponds to exactly one element
of $\cal C$ and no two distinct natural numbers correspond to the
same element of $\cal C$.  Furthermore, choose your correspondence
so as to preserve addition.  That is,
the element corresponding to the sum of two natural
numbers must be the sum of their corresponding elements of $\cal C$. \\
f.  Describe all possible ways of setting up a correspondence meeting
the requirements of part e.  Prove that all of the correspondences you
have described work.  (Note that this does not prove that your answer is
correct.  That would also require showing that no other correspondences
work.) \\
g.  What is the smallest set containing the natural numbers whose members
can be paired up with all the members of $\cal C$ in a way that preserves
addition?  How many such pairings are possible using this set?

\noindent 1. a.  Specify a state machine that shuffles a standard deck of
52 cards.  That is, you should have a code fragment that corresponds to
cutting the deck into two pieces at an arbitrary point.  You should
also have code fragments corresponding to moving a card from the bottom
of either of the pieces to the top of the new stack.  Prove that the
result after any number of shuffles still has the original 52 cards. \\
b. Specify a new state machine that is like that in part a with the
following exceptions.
All start states have the deck alternating between red and black cards.
Whenever the deck is cut, each piece must have an even number of cards.
Cards must be removed from each piece in pairs (not necessarily in
one transition, but without an intervening transfer from the other piece).
Prove that the cards will always remain alternating between red and black.
\\


\problem
\noindent We define the $TreeBuilder$ state machine as given below.

\vspace{.12in}
\noindent
%\footnotesize

%\footnotesize
\noindent
{\bf States:} \nobreak
\vspace{.12in}

\begin{quote} \nobreak
$\ms{V}$, a set of vertices, with initial set $V_0 = \{v_0\}$\\
$\ms{E}$, a subset of $V \times V$, initially empty\\
$\ms{n}$, an element of $\cal N$, initially $n = 1$\\

\end{quote}
\normalsize
\noindent


%\footnotesize
\noindent
{\bf Transitions:}

\normalsize 

$\ms{expand(v,w,x)}$


{\bf Precondition:}

  $v \in V$\\
  There is at most one edge incident on $v$ in $E$


{\bf Effect:}

  $V := V \cup \{w,x\}$\\
  $E := E \cup \{(v,w), (v,x)\}$\\
  $n := n +2$

 
\vspace{.12in}

\noindent Now prove the following $3$ invariants (in order):
\begin{itemize}
\item $|V| = n$
\item $(V,E)$ is a tree
\item If $|V| \geq 2$, then $(V,E)$ has $(n-1)/2$ internal nodes
\end {itemize}

\problem % Subtraction based GCD algorithm.

Consider a state machine whose states consists of 
values for the following variables:

\begin{tabbing}
XXX\=XXX\= \kill
\> $\ms{x} \in I\!\! N$ \\
\> $\ms{y} \in I\!\! N$ \\
\> $\ms{x'} \in I\!\! N$ \\
\> $\ms{y'} \in I\!\! N$ \\
\end{tabbing}

The initial states are those such that $x=x'$ and $y=y'$.
The values $(x,y)$ are the input to the machine.

The transitions are of the following two kinds:

\iocode{

\prcef{$\ms{swap}$}
{% Precondition: \\
   $\ms{x'} < \ms{y'}$}
{% Effect: \\
   $(\ms{x'},\ms{y'}) := (\ms{y'},\ms{x'})$}
}{
\prcef{$\ms{subtract}$}
{% Precondition: \\
   $\ms{x'} \geq \ms{y'} > 0$}
{% Effect: \\
   $(\ms{x'},\ms{y'}) := (\ms{x'}-\ms{y'},\ms{y'})$}
}

When the machine terminates, the value of $x'$
is output.

What is the function computed by the machine?
Prove your answer using the invariant method.


\problem  Let Delete($M$, $i$, $j$) represent the matrix obtained
from deleting the $i$th row and the $j$th column from $M$.  Either
prove that the following algorithm correctly computes the determinant of
a matrix (by the Co-factor Method) or provide a counter-example.
Assume $M$ is a $size[M] \times size[M]$ matrix.

\begin{tabbing}

Det($M$) \\
\ \ \ \= if ($size[M] = 1$) \\
      \> \ \ \ \= return($M_{1,1}$) \\
      \> $x \leftarrow 0$ \\
      \> $\sigma \leftarrow 1$ \\
      \> for $i$ = 1 to $size[M]$ \\
      \>        \> $x \leftarrow x + \sigma \cdot M_{i,1} \cdot
\mbox{Det( Delete}(M, i, 1))$ \\
      \>        \> $\sigma \leftarrow -\sigma $ \\
      \> return($x$) \\
\end{tabbing}

\problem 

A friend of yours who works at Toasters 'R Us, has intercepted the secret
plans for the next generation of toaster ovens run by cheap processors.
(perhaps to make sure your toast doesn't burn).  The
processors can only add and subtract numbers. He hands you the following 
code.  Determine what it does and prove that it does it and terminates in 
finite time.

\begin{verbatim}
i_like_to_add(x)
{ 
  sum=0;
  i=1;
  while (i<n) {
    sum = sum + 2*i;
    i=i+1;
  }
  sum = sum+n;
  return(sum);
}
\end{verbatim}

\problem  We define a state machine $S$, whose set of states are determined
by the following state variables:

\hspace{0.5in} $x \in \naturals$

\hspace{0.5in} $y \in \naturals$ 

\hspace{0.5in} $x' \in \naturals$ 

\hspace{0.5in} $y' \in \naturals$ 

\hspace{0.5in} $a \in \naturals$.

The start states are those for which $x = x'$, $y = y'$, and $a = 0$.
The transitions are as follows: \\

\hspace{1in}{\em remove-zero} 

\hspace{1.2in} Precondition: 

\hspace{1.4in} $x'$ is even 

\hspace{1.4in} $x' \neq 0$ 

\hspace{1.2in} Effect: 

\hspace{1.4in} $x' := x'/2$ \\

\hspace{1in} {\em remove-one} 

\hspace{1.2in} Precondition: 

\hspace{1.4in} $x'$ is odd 

\hspace{1.2in} Effect: 

\hspace{1.4in} $x' := (x'-1)/2$ 

\hspace{1.4in} $a := a + 1$ \\

\hspace{1in} {\em swap} 

\hspace{1.2in} Precondition: 

\hspace{1.4in} $x' \neq 0$ or $y' \neq 0$ 

\hspace{1.2in} Effect: 

\hspace{1.4in} swap($x$, $y$) 

\hspace{1.4in} swap($x'$, $y'$) \\

Prove that if $S$ finishes, the final state will have $a = 0$ if the
sum of the digits (in binary) of the original values of $x$ and $y$ is even and
will have $a = 1$ otherwise. \\

\problem 
A binary search tree is a binary tree where each node has a value (we 
will assume each
node has a distinct value), and which is goverened by the following rules: \\
For all nodes, 
\begin{itemize}
\item 
If a node has a left child then the $value(node) > value(LeftChild)$.
\item 
If a node has a right child then the $value(RightChild) > value(node)$
\end{itemize}

Prove that the following algorithm prints out all the values in a binary search
tree in increasing order.

\begin{verbatim}
traverse(node)
  if (node has a left child) then
    traverse(left subtree)
  print(node's value)
  if (node has a right child) then
    traverse(right child)

\end{verbatim}

\problem
  Let $A$ be an infinite sequence of real numbers such that
$$A_n \leq A_{n+2} \ \forall n \in \naturals \mbox{and}$$
$$A_n \leq A_{n+3} \ \forall n \in \naturals.$$
The search problem in $A$ is defined as follows.  Given a
real number $r$ and natural numbers $i, j$, find an index $m$ such
that $i \leq m \leq j$ and $A_m = r$.
The following algorithm is supposed to solve the search problem if
possible and return the special value {\em missing} otherwise.



\begin{tabbing}

Find($r$, $i$, $j$) \\
\ \ \ \= if ($j - i < 5$) \\
      \> \ \ \ \= $l \leftarrow i$ \\
      \>       \> while (($l \leq j$) and ($A_l \not = r$)) \\
      \>       \> \ \ \ \= $l \leftarrow l + 1$ \\
      \>       \> if ($l \leq j$) \\
      \>       \>       \> return($l$) \\
      \>       \> else \\
      \>       \>       \> return({\em missing}) \\
      \> else \\
      \>       \> $k \leftarrow \lfloor \frac{i + j}{2} \rfloor$ \\
      \>       \> if ($A_k > r$) \\
      \>       \>       \> return Find($r$, $i$, $k + 1$) \\
      \>       \> else \\
      \>       \>       \> return Find($r$, $k - 1$, $j$) \\
\end{tabbing}

Either prove the algorithm correct or find a counter-example.



1.  Prove by induction that  $\Sum_{j \leq i \leq 1}(6i^2 -4i -3)
    = -2j^3 + 5j^2 -4 \forall j \leq 1$.

2.  Classify the pairs of natural numbers $m$ and $n$ for which there
    exist integers $i, j$ such that $im + 4j = 5^n$.  Prove that all of
    the pairs you allow do have such integers and that no other pairs do.

3.  Define a sequence of natural numbers $A_n$ by $A_0 = 0$, $A_1 = 1$,
    and $A_{n+2} = 5A_{n+1} - 6A_n$ for $n /geq 0$.  Give a formula for
    $A_n$ and prove it correct.

Consider the sequence g_0=a, g_1=b, g_{n}=g_{n+1}+g_{n+2}.  Give and
prove a solution to this recurrence in terms of a,b, and the fibonacci
numbers.


In propositional logic, well formed formulas (WFF) 
are defined recursively as follows. 
Any atomic proposition $P$ is a WFF.
If $f$ is a WFF then $\neg f$ is a WFF.
If $f$ and $g$ are WFF then $f\vee g$ and 
$f\wedge g$ are WFF.

A conjunctive normal form (CNF) is a WFF
\[ (L_{1,1}\vee L_{1,2} \vee \cdots \vee L_{1,n_1})
 \wedge (L_{2,1}\vee L_{2,2} \vee \cdots \vee L_{2,n_2})
 \wedge \cdots
 \wedge (L_{m,1}\vee L_{m,2} \vee \cdots \vee L_{m,n_m})
\]
where each $L_{i,j}$ is either an atomic proposition ($P$) or 
the negation of an atomic proposition ($\neg P$).

Prove by structural induction that any WFF is equivalent to a CNF.
You may use the logical equivalences given in Rosen page 17.
({\em Hint:} you may need to strengthen the hypothesis.)


\newcommand{\ef}[2]{
\begin{tabbing}       
XX\= XX\=XX\=XX\=XX\=XX\=   \kill
\protect #1\\
\>Effect: \+ \+ \\ 
   #2  \- \-
\end{tabbing}}

\newcommand{\iocode}[2]{\begin{center}\footnotesize
\begin{minipage}[t]{.45\linewidth}
\hbox to\linewidth{}
#1
\end{minipage}
\hspace{.05\linewidth} 
\begin{minipage}[t]{.45\linewidth}
\hbox to\linewidth{}
#2
\end{minipage}
\end{center}}

\newcommand{\prcef}[3]{\begin{tabbing}       
XX\=  XX\=XX\=XX\=XX\=  \kill
\protect #1\\
\>Precondition: \+ \+ \\ 
  #2  \-  \- \\ 
\>Effect: \+  \+ \\
  #3 \- \- 
\end{tabbing}} 

\problem

Consider a coin exchanger described by the 
following state machine.

The state set $Q$ consists of values for state components:
\begin{tabbing}
XXX\=XXX\= \kill
\> $\ms{total} \in I\!\! N$ \\
\> $\ms{total'} \in I\!\! N$ \\
\> $\ms{cents} \in I\!\! N$ \\
\> $\ms{dimes} \in I\!\! N$ \\
\> $\ms{quarters} \in I\!\! N.$ \\
\end{tabbing}

Here $\ms{total}$ is an initial amount of money (in cents) given 
as input to the machine.
All other variables are initially set to $0$.
When the machine terminates (no more transitions are possible)
the variables $\ms{cents}, \ms{dimes}$ and $\ms{quarters}$
should be the correct change corresponding 
to the input $\ms{total}$.
$\ms{total'}$ is an auxiliary variable.

The transition function $\delta$ is defined by the 
following rules.


\iocode{

\prcef{$\ms{give-quarter}$}
{% Precondition: \\
   $\ms{total}-\ms{total'} \geq 25$}
{% Effect: \\
   $\ms{total'} := \ms{total'} + 25$ \\
   $\ms{quarters} := \ms{quarters} + 1$}

\prcef{$\ms{give-dime}$}
{% Precondition: \\
   $25 > \ms{total}-\ms{total'} \geq 10$}
{% Effect: \\
   $\ms{total'} := \ms{total'} + 10$ \\
   $\ms{dimes} := \ms{dimes} + 1$}

}{

\prcef{$\ms{give-cent}$}
{% Precondition: \\
   $\ms{total}-\ms{total'} < 10$}
{% Effect: \\
   $\ms{total'} := \ms{total'} + 1$ \\
   $\ms{cents} := \ms{cents} + 1$}
}

Prove using the invariant method that the algorithm is correct,
that is, when the machine terminates the total amount of 
money described by the variables
$\ms{cents}, \ms{dimes}, \ms{quarters}$
is exactly $\ms{total}$.

\problem % Subtraction based GCD algorithm.

Consider a state machine whose states consists of 
values for the following variables:

\begin{tabbing}
XXX\=XXX\= \kill
\> $\ms{x} \in I\!\! N$ \\
\> $\ms{y} \in I\!\! N$ \\
\> $\ms{x'} \in I\!\! N$ \\
\> $\ms{y'} \in I\!\! N$ \\
\end{tabbing}

The initial states are those such that $x=x'$ and $y=y'$.
The values $(x,y)$ are the input to the machine.

The transitions are of the following two kinds:

\iocode{

\prcef{$\ms{swap}$}
{% Precondition: \\
   $\ms{x'} < \ms{y'}$}
{% Effect: \\
   $(\ms{x'},\ms{y'}) := (\ms{y'},\ms{x'})$}
}{
\prcef{$\ms{subtract}$}
{% Precondition: \\
   $\ms{x'} \geq \ms{y'} > 0$}
{% Effect: \\
   $(\ms{x'},\ms{y'}) := (\ms{x'}-\ms{y'},\ms{y'})$}
}

When the machine terminates, the value of $x'$
is output.

What is the function computed by the machine?
Prove your answer using the invariant method.


\problem  We define a state machine $S$, whose set of states are determined
by the following state variables:

\hspace{0.5in} $x \in \naturals$

\hspace{0.5in} $y \in \naturals$ 

\hspace{0.5in} $x' \in \naturals$ 

\hspace{0.5in} $y' \in \naturals$ 

\hspace{0.5in} $a \in \naturals$.

The start states are those for which $x = x'$, $y = y'$, and $a = 0$.
The transitions are as follows: \\

\hspace{1in}{\em remove-zero} 

\hspace{1.2in} Precondition: 

\hspace{1.4in} $x'$ is even 

\hspace{1.4in} $x' \neq 0$ 

\hspace{1.2in} Effect: 

\hspace{1.4in} $x' := x'/2$ \\

\hspace{1in} {\em remove-one} 

\hspace{1.2in} Precondition: 

\hspace{1.4in} $x'$ is odd 

\hspace{1.2in} Effect: 

\hspace{1.4in} $x' := (x'-1)/2$ 

\hspace{1.4in} $a := a + 1$ \\

\hspace{1in} {\em swap} 

\hspace{1.2in} Precondition: 

\hspace{1.4in} $x' \neq 0$ or $y' \neq 0$ 

\hspace{1.2in} Effect: 

\hspace{1.4in} swap($x$, $y$) 

\hspace{1.4in} swap($x'$, $y'$) \\

Prove that if $S$ finishes, the final state will have $a = 0$ if the
sum of the digits (in binary) of the original values of $x$ and $y$ is even and
will have $a = 1$ otherwise. \\

\problem  We define a {\em polyclump} to be:

\begin{itemize}

   \item A triangle. In this case, its vertices and sides are defined
         to be the same as those of the triangle and it is defined
         to have exactly one polygon, which is the triangle itself.

   \item The union of a polyclump and a triangle sharing a common side
         with some polygon of the polyclump.  The triangle is not allowed to
         be contained by that polygon and no part of the triangle except
         for that side is allowed to intersect any polygons of the polyclump.
         In this case, the vertices and sides are the union of those of
         the polyclump and the triangle, and the polygons are the triangle
         and those of the polyclump.

   \item The same as above, except that the triangle is merged with the
         polygon of the polyclump with which it shares a side so that
         this side is not a side of the bigger polyclump and these two
         polygons are not polygons of the bigger polyclump, but their
         union is instead.

\end{itemize}

Give an informal description of what polyclumps look like.  You do not
have to prove your description correct.
Prove that the number of polygons in a polyclump is one more than the
number of edges minus the number of vertices.
What does this have to do with 3-dimensional polyhedra?


\problem
Show that if $a$ is an integer and $d \geq 1$, then the quotient and remainder
 obtained when $a$ is divided by $d$ are $\lfloor a/d \rfloor$ and 
$a-d \lfloor a/d \rfloor$, respectively.

% Local Variables: 
% mode: latex
% TeX-master: t
% End: 
