\documentstyle[12pt,twoside,amstex]{article}

\addtolength{\topmargin}{-1in}
\setlength{\textwidth}{6.5in}
\setlength{\textheight}{9in}

\raggedbottom

\input{macros-course}

\begin{document}

\handout{recprobs4}{Problems for Recitation 4}{February 27, 1998}

%\section*{Team Problems}

\begin{problems}

\problem Fast multiplication by adding and doubling.

Consider the following multiplication algorithm, known as the ``Russian
peasant's multiplication'' to multiply numbers $x,y \in naturals$.

The accumulator for the answer is register \texttt{a}; registers
\texttt{r}, \texttt{s} are for temporary storage.

\begin{verbatim}
r:=x; s:=y; a:=0;
Do until s=0:
 if even(s) then {r := 2r; s := s/2};
 if odd(s) then {a := a + r; r := 2r; s := (s-1)/2};
\end{verbatim}
The answer $xy$ will be left in the accumulator \texttt{a} when the
procedure terinates.

Here is an example of the execution of the algorithm.
\begin{verbatim}
 x     y     r     s     a
 -------------------------
 5     9     5     9     0
            10     4     5
            20     2     5
            40     1     5
            80     0    45
\end{verbatim}

Model the computation as a state machine.  Prove it terminates using a
derived variable.  Prove that it is correct using an invariant.

\problem Instability in Unisex Marriage.

We might better call this the Buddy Pairing Problem: an even number of
men, each with a preference ranking of all the others, to be paired as
``buddies'' in a stable way.

Derive an example of preferences for this unisex version of the mating
problem which shows that it is \emph{not} possible to always pair all the
players so that the marriages satisfy the stability criterion.  \hint
Consider just four men.


\problem

The judge says to the guilty defendant,
\begin{quotation}
\noindent ``Here is what is called a \emph{Petition Process}:
\begin{quotation}
\noindent You may name a number of times you may petition me.  Your
petitions may request a number of times you may start a count of days till
your next petition or until this whole petition process shall end.  Your
petitions will be granted.  When the number of days named in your last
petition is reached, the process will end.
\end{quotation}

\noindent Now you may request a number of petition processes in which you would like
to participate.  Your request will be granted, but at the end of the last
process, your head will be cut off.''
\end{quotation}
The defendant responds, ``I want to participate in 2 processes.''  The
judge says ``OK'', and the defendant asks to submit 4 petitions.  The
judge says ``OK,'' and the defendant files a petition asking for 10 days.
The judge says ``OK.''  10 days later, the defendant files a petition
asking for 20 days.  20 days later the defendant asks for 30 days, and 30 days
later for 40 days.

40 days later, he starts his second petition process, this time asking to
submit 3 petitions.  The first petition is for 100 days.  100 days later,
he asks for 200 days.  200 days later he asks for 300 days.  300 days
later his head gets cut off \texttt{:-(}.

Of course a smarter prisoner could have named much larger numbers and
lived out his natural lifetime.  But for the sake of philosophy, suppose
the prisoner (and the judge and executioner) will live as long as it takes
to get executed.  Prove that the prisoner will always eventually get
executed.

\problem Consider the Stable Marriage Problem when there are more men than
women.  Define what a set of stable marriages should mean in the presence
of bachelors.  Show that the Morning-Afternoon-Evening Protocol described
in lecture solves this Marriage Problem.

\end{problems}

\end{document}
