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

\askaboutsolutions

\begin{document}

%% TUTORIAL 6: Computational Processes (Rad, Fall01)
\ifshowsolutions
  \tutsol{6}{October 11, 2001}{\stamp}
\else
  \tutprobn{6}{October 11, 2001}{\stamp}
\fi

\begin{problems}

%------------------------------------------------
% source: karger tut5, old problems
% topic: 15 puzzle, state machine
% last used:

\problem The Fifteen Puzzle consists of sliding square tiles numbered
$1,\dots,15$ held in a $4\times4$ frame with one blank square.  Any tile
adjacent to the blank square can slide into it.

The state machine model of the puzzle has states consisting of a $4\times
4$ matrix with 16 entries consisting of the integers $1,\dots,15$ and a
blank.  For example, the standard initial position is
\[\begin{array}{|c|c|c|c|}
\hline 1 & 2 & 3 & 4\\
\hline 5 & 6 & 7 & 8\\
\hline 9 & 10 & 11 & 12\\
\hline 13 & 14  & 15 & \\
\hline
\end{array}\]
We would like to reach the target position (known in my youth as ``the
impossible'' --- ARM):
\[\begin{array}{|c|c|c|c|}
\hline 15 & 14 & 13 & 12\\
\hline 11 & 10 & 9 & 8\\
\hline7 & 6 & 5 & 4\\
\hline3 & 2 & 1 & \\
\hline
\end{array}\]

The state transitions correspond to exchanging the blank square and an
adjacent numbered tile.  For example, a blank at position $(2,2)$ can
exchange position with tile above it, namely, at position $(1,2)$:
\[\begin{array}{|c|c|c|c|}
\hline n_1 & n_2 & n_3 & n_4\\
\hline n_5 &  & n_6 & n_7\\
\hline n_8  & n_9 & n_{10} & n_{11}\\
\hline n_{12} & n_{13} & n_{14}  & n_{15}\\
\hline
\end{array} \longrightarrow
\begin{array}{|c|c|c|c|}
\hline n_1 &  & n_3 & n_4\\
\hline n_5 & n_2 & n_6 & n_7\\
\hline n_8  & n_9 & n_{10} & n_{11}\\
\hline n_{12} & n_{13} & n_{14}  & n_{15}\\
\hline
\end{array} 
\]

In this problem you will use the invariant method prove that starting
from the initial state, there is no way to reach the target state.

We begin by noting that a state can also be represented as a pair
consisting of two
things:
\begin{enumerate}

\item a list of the numbers $1,\dots,15$ in the order in which they
appear---reading rows left-to-right from the top row down, ignoring the
blank square, and

\item the coordinates of the blank square---where the upper left
square has coordinates $(1,1)$, the lower right $(4,4)$.

\end{enumerate}

Let $L$ be such an ordered list of the numbers $1,\dots,15$.  A pair
of integers is an \emph{out-of-order pair} in $L$ when the first
element of the pair both comes earlier in the list, and is larger,
than the second element of the pair. For example, the list $1,2,4,5,3$
has two out-of-order pairs: 4,3 and 5,3.  The increasing list
$1,2\dots n$ has no out-of-order pairs.

\bparts

Representing a state, $S$, as the pair $(L, (i,j))$ described above,
define the \emph{parity} of $S$ to be the mod 2 sum of the number of
out-of-order pairs in $L$ and the row-number, $i$, of the blank
square.

\ppart Verify that the parity of the initial state and the parity of the
target state are different.

\solnospace{The parity of the initial state is $(0+4) \bmod 2 = 0$.
Parity of target is $((15 \cdot 14/ 2) + 4) \bmod 2 = 1$.}

\ppart Show that the parity of a state is invariant under transitions.
Conclude that ``the impossible'' is impossible to reach.

\solnospace{To show that the parity is constant, let us consider what
types of moves may affect the parity.  The only 4 moves we need to worry
about are the following:  a move to the left, a move to the right, a move
to the row above, or a move to the row below.  
Note that horizontal moves change nothing, and vertical moves both change 
$i$ by 1, and move a tile three places forward or back in the list, $L$.  
To conside how the parity is changed in this case, we need to consider
only the 3 pairs in $L$ that are between the tile's old and new position.
(The other pairs are not effected by the tile's move).  
This reverses the order of three pairs in $L$, changing the number of
inversions by 3 or 1, but always by an odd amount.  (If the 3 pairs were 
all out of order or all in order before, the amount is changed by 3.  If 
two pairs were out of order and 1 pair was in order or if one pair
was out of order and two were in order, this will change the amount by 1.  
So the sum of $i$ and the number of out-of-order pairs changes by an even 
amount (either 1+3 or 1+1), which implies that its parity remains the same.  
Since the initial state has parity 0 (even), all states reachable from the 
initial state must have parity 0, so the target state with parity 1 can't be 
reachable.
}

\eparts

%Fast multiplication by adding and doubling from F97 pset4, problem 2.

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

The accumulator for the answer is register \texttt{p}; registers
\texttt{x}, \texttt{y} are for temporary storage.

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

Here is an example of the execution of the algorithm for $a=5, b = 9$:
\begin{center}
\begin{verbatim}
 x     y     p
--------------
 5     9     0
10     4     5
20     2     5
40     1     5
80     0    45
\end{verbatim}
\end{center}

\bparts

\ppart
Model the algorithm as a state machine.  

\solnospace{The state is the triple of values in $x$, $y$, and $p$.

There is just one start state: $(a,b,0)$.

There are two types of state transitions (even or odd) as described in the
algorithm.  Consider a transition from $(x,y,p)$ to $(x',y',p')$:

if y is even:   $(x',y',p')$ = $(2x, y/2, p)$

if y is odd:    $(x',y',p')$ = $(2x, (y-1)/2, p+x)$
}

\ppart
Prove that it terminates using a
derived variable.  

\solnospace{ Notice that a decreasing variable for this algorithm is 
$y$.  At each step, if $y$ is even, it becomes $y/2$ and if $y$ is odd, it
becomes $(y-1)/2$.  We can clearly see that $y$ will eventually become 0
and the algorithm must terminate.

Furthermore, we can say even more about when the algorithm will terminate.

\begin{theorem}
The algorithm terminates in at most $\floor{\log_2 b}+1$ steps.
\end{theorem}

\begin{proof}
Define the derived variable $f(x,y,p) = \floor{\log_2 y}+1$.  Notice
that $f$ is decreasing, since at each step $y'$ becomes $\frac{y}{2}$ if
$y$ is even and $\frac{y-1}{2}$ if $y$ is odd.  So the length of an
execution is at most $f(q_0) = f(a,b,0) \leq \floor{\log_2 b}+1$.
\end{proof}
}

\ppart
Prove that it is correct using an invariant.

\solnospace{
To prove correctness, we show that
\begin{lemma*}
The predicate $P(x,y,p) \eqdef\ [ab = xy+p]$ is an invariant.
\end{lemma*}

\begin{proof}
Consider a transition from $(x,y,p)$ to $(x',y',p')$ and suppose
$P(x,y,p)$ holds, that is, $ab = xy+p$.  We must prove that $P(x',y',p')$
holds, that is, $ab = xy+p$.  There are two cases based on the type of
action, \emph{even} or {\it odd}.

\emph{even}: Doubling $x$ while halving $y$ doesn't change the product
$xy$, and $p$ doesn't change.  So $x'y'+p' = xy+p = ab$.

\emph{odd}: $x' = 2x$, $y' = (y - 1)/ 2$, and $p' = p + x$.  So
\[
x'y' + p' = 2x(y - 1)/ 2 + p + x = (xy-x) + p + x = xy+p = ab.
\]
\end{proof}

Also, $P$ holds for the start state $(a,b,0)$ because $ab+0 = ab$.  So by
the Invariant Theorem, we conclude:
\begin{corollary*}
If $y=0$ in a reachable state, then $p = ab$.
\end{corollary*}

\begin{proof}
By our invariant, we have
$P(x,0,p)$, that is $x0 + p = ab$, so $x=ab$.
\end{proof}
}

\eparts

%------------------------------------------------
% source: karger tut5, old problems
% topic: marriage problem (simple)
% last used:

\problem Four people are interested in participating in the VI-A
program where each person ranks his top choices of companies and the
companies rank the students as well.  The people Albert, Jaime, Christos,
and Thien-loc are interested in companies AT\&T, Bellcore, Compaq, and
Draper Labs.  Below are the students' rankings of the companies and
the companies' rankings of the students.

\begin{center}
\begin{tabular}{c|c} 
Student & Companies \\ \hline
Albert:  & Compaq, Bellcore, AT\&T, Draper \\
Jaime:     & AT\&T, Bellcore, Draper, Compaq \\
Christos:   & Compaq, Draper, AT\&T, Bellcore \\
Thien-loc:    & Draper, AT\&T, Bellcore, Compaq 
\end{tabular}
\end{center}

\begin{center}
\begin{tabular}{c|c}
Company   & Students \\ \hline
AT\&T:    & Thien-loc, Albert, Christos, Jaime \\
Bellcore: & Christos, Jaime, Albert, Thien-loc \\
Compaq:   & Thien-loc, Christos, Albert, Jaime \\
Draper:   & Jaime, Thien-loc, Christos, Albert
\end{tabular}
\end{center}

\begin{problemparts}
\problempart What is a student-optimal stable marriage set for
this problem?

\solnospace{
You were guaranteed to get a student-optimal stable marriage set if
you ran the stable marriage algorithm given in lecture, where Students
are Men and Companies are Women.  The result is the following assignment:

\begin{center}
\begin{tabular}{c|c|c} 
Student & Companies & Rank in the original list \\ \hline
Albert:  & Bellcore & 2\\
Jaime:     & AT\&T & 1\\
Christos:   & Compaq & 1\\
Thien-loc:    & Draper &1
\end{tabular}
\end{center}
}

\problempart What is a company-optimal stable marriage set for
this problem?

\solnospace{Similarly, you were guaranteed to get a company-optimal
stable marriage set if you ran the stable marriage algorithm given in
lecture, where Students are Women and Companies are Men.  The result
is the following assignment:

\begin{center}
\begin{tabular}{c|c|c}
Company & Students & Rank in the original list\\ \hline
AT\&T:    & Albert & 2\\
Bellcore: & Jaime & 2\\
Compaq:   & Christos & 2\\
Draper:   & Thien-loc & 2
\end{tabular}
\end{center}
}

% source: Fall 2000 Problem Set 5
% topics: Matching, intuition

\ppart Give an example of a stable match between 3 boys and 3 girls
where no person gets their first choice.

\solnospace{Call the boys $1, 2, 3$ and the girls $a, b, c$.  Consider
the following preference list:

\begin{center}
\begin{tabular}{llll||llll} \hline
choice& 1st& 2nd& 3rd& choice& 1st& 2nd& 3rd \\ \hline
1& a& b& c& a& 2& 3& 1 \\
2& b& c& a& b& 3& 1& 2 \\
3& c& a& b& c& 1& 2& 3 \\ \hline
\end{tabular}
\end{center}
   
The matching $(1, b), (2, c), (3, a)$ is stable even though no person
gets their first choice.  

To see the intuition behind this solution, notice first that the first
choice of any boy has that boy as her last choice and vice versa.  
Second, notice that everyone ends up with their second choice.  

Since we show a pairing where everyone has their second choice, this 
is stable because the only way to have a rogue pair is for a boy
or girl to want their first choice, but their first choice always 
likes them least so will never want to leave their current partner.  
Therefore, we end up with a stable pairing where no one gets their
first choice.}

%\ppart Can a stable match where no person gets their first choice be
%produced by the matching algorithm described in the lecture notes?  If
%yes, state an example and show why the example works.  If not, prove
%using an invariant.

%\solnospace{Yes. For $n=4$, for boys $1, 2, 3, 4$ and the girls $a, b,
%c, d$, the following preference list yields such a match (x choices
%don't matter):
%
%\begin{center}
%\begin{tabular}{lllll||lllll} \hline
%choice& 1st& 2nd& 3rd& 4th& choice& 1st& 2nd& 3rd& 4th \\ \hline
%1& a& c& x& x& a& 3& 2& 1& 4 \\
%2& b& a& x& x& b& 1& 4& 3& 2 \\
%3& b& d& x& x& c& x& 1& x& x \\
%4& a& b& x& x& d& x& 3& x& x \\ \hline
%\end{tabular}
%\end{center}

%The matching algorithm executes as follows:%
%
%\begin{description}
%\item[Round 1] $a$ picks $1$. $b$ picks $3$. $2, 4$ are dropped.
%\item[Round 2] $a$ picks $2$. $b$ picks $4$. $1, 3$ are dropped.
%\item[Round 3] $c$ picks $1$. $d$ picks $3$.
%\end{description}
%}

\end{problemparts}


\problem The Stable Buddy Problem is a variant of the Stable Marriage
Problem without the constraint that matched pairs must be boy with girl.

Namely, in the Buddy Problem, there is an even number of people, each with
their own preference ranking of all the other people.  The population is
supposed to be organized into separate pairs of people --- the two members
of a pair are called ``buddies''.  Such an assignment of buddies is
\emph{unstable} if there are two people who are not each other's buddies,
but who would prefer to be buddies with each other rather than being with
their assigned buddies.

In contrast to the Stable Marriage Problem, there are preference listings
where all buddy assignments are unstable.  Give an example of four people
and their preference rankings of the other three people for which there is
no stable way to assign buddies.

\solnospace{Let the buddy preferences of four men A, B, C, D be\\
A: BCD\\
B: CAD\\
C: ABD\\
D: $?\: ?\: ?$

Let Y and Z be any two among A, B, and C, and let X be the remaining one.
Notice that the first choices of A, B, C are arranged in a cycle, so that
X must be the first choice of either Y or Z.

Now for any matching into pairs, let Y and Z be the two among A, B, C who
are paired, and X be the one paired with D.  So one of Y and Z, say Y, has X
as his first choice.  But since A, B, C each rank D last, X prefers Y to
his own buddy, D.  So X, Y are a rogue couple.  Notice that the ranking of
A, B, C by D doesn't matter.
}

\end{problems}
\end{document}


