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

\begin{document}
\pset{4}{September 23, 1997}{Tuesday, September 30}

{\bf Reading assignment: Chapter 6 of Rosen, 2.1-2.4 and 3.3-3.5.
 Section 2.5 is interesting but optional}


\begin{problems}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%problem 1
\problem{\bf [40 points]}
 
In this problem you are asked to design a
protocol for college admissions. The protocol must have the following 
properties:  

There are $N$ students $S_1,...,S_N$ and $M$ universities $U_1,...,U_M$.  
Each student provides a preference ranking of all $M$ universities and each 
university provides a preference ranking of all $N$ students.  
For each $i$ university $U_i$ has $n_i$ slots to fill
and sum of all slots is equal to the number of students. 
That is, $\sum_{i=1}^M n_i = N$.  
The protocol should assign every student to a university so that

\begin{enumerate}

\item For each $i$ University $U_i$ gets $n_i$ students, 

\item There does not exist students $S_i, S_j$
and universities  $U_k, U_l$ where $S_i$ is assigned to
$U_k$ and $S_j$ is assigned to $U_l$, but 
$S_j$ prefers $U_k$ to $U_l$, and $U_k$ prefers $S_j$ to $S_i$.

\item The assignment algorithm should be student optimal in the sense
that every student gets their top choice among all assignments that
satisfy conditions 1 and 2 above.

\end{enumerate}

\bparts
\ppart{\bf [8 points]}
Model the problem as a state machine.  State clearly what the states and
state transitions are. What is the start state? 

\ppart{\bf [8 points]}
Use derived variables to prove termination.
How long does the protocol take to terminate?

\ppart{\bf [8 points]}
Prove that every student is assigned and every university gets the
right number of students. 

\ppart{\bf [8 points]}
Prove that there are no assignments violating condition 2. 

\ppart{\bf [8 points]}
Prove that condition 3 holds. 

\eparts


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%problem 2
%Russian peasant from spring97 lecture 7
\problem{\bf [20 points]} 

Consider the following multiplication algorithm ,known as the
``Russian peasant's multiplication''


$x$, $y$, are arbitrary positive integers whose values are to be multiplied.
$a$, is the accumulator for the answer. \\
$r$, $s$, are temporary variables. \\

Initially, $r = x$, $s = y$, $a = 0$. We denote the next value of $r$ 
by $r'$, etc...


Do until $s=0$

If $s$ is even and $s > 0$,\\
$r' := 2r$ \\
$s' := {s \over 2}$ \\

If $s$ is odd,\\
$a' := a + r$ \\
$r' := 2r$ \\
$s' := {s-1 \over 2}$ \\

The answer is the value in the accumulator $a$ when $s = 0$. \\
\\
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 3
\problem{\bf [10 points]}

Evaluate $\gcd(F_n, F_{n-1})$ for any $n$, where $F_n$ is the $n$th Fibonacci
number.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%problem 4
\problem{\bf [10 points]} 

Derive an example of preferences for the unisex
version of the mating problem (all boys or all girls)
which show that it is not possible to
always pair all the players so that the marriages satisfy the
stability criterion.  

{\it (Hint: 4 people is enough)}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%problem 5
\problem{\bf [20 points]}
%make a robot movement problem in 3d where they need to use an
%invariant and/or state machine.

Luke Skywalker is using a training device (like the one in Starwars I)
to develop his light-saber fencing skills.  The training device is a contraption
that in every time step makes a move in a three dimensional grid and emits a
non-lethal laser beam.  
This particular training device can only move as follows:
At every step it can move 1 unit north or south AND 1 unit east or west 
AND 1 unit up or down. 
Luke is using the Force to guide his feelings but also common sense to guard
against possible attack points.

If the device starts at position $(0,0,0)$, should Luke ever guard against an
attack coming from position $(1,1,2)$?  Prove your answer using state machines
and invariants.

{\it (Note:  There are many invariants that will work for this problem.)}


\end{problems}
\end{document}








