\documentstyle[12pt]{article}
\setlength{\topmargin}{-0.50in}
\setlength{\textheight}{8.5in}
\setlength{\oddsidemargin}{0.0in}
\setlength{\evensidemargin}{-0.0in}
\setlength{\textwidth}{6.5in}
\addtolength{\parskip}{2pt}
\addtolength{\itemsep}{0.1in}
\newtheorem{theorem}{Theorem}
\newtheorem{definition}{Definition}
\newtheorem{claim}{Claim}
\newtheorem{lemma}{Lemma}
\newtheorem{fact}{Fact}
\newtheorem{corollary}[theorem]{Corollary}
\newcommand{\qed}{\mbox{\ \ \ }\rule{6pt}{7pt} \bigskip}

\begin{document}

{\bf Tutorial 4 solutions }

\date{}

\begin{enumerate}
\item {\em Efficiency of Euclid's algorithm. } 
\begin{enumerate}
\item Show that Euclid's GCD algorithm uses at most $2 \log_2 x$ 
modulo operations. [Use derived variables]

Derived variable: $f((a,b)) = a$

\begin{claim}
If $x > y > 0$ then
for any pair of transitions, $q \rightarrow q_1 \rightarrow q_2$, 
$f(q_2) \leq \frac{1}{2}f(q_2)$, i.e. $f$ halves every two steps.
\end{claim}
{\em Proof. }
We consider two cases: 
\begin{enumerate}
 \item $f(q_1) \leq f(q)/2$. 

In this case, since $f$ is a decreasing variable, 
$f(q_2) \leq f(q_1)\leq f(q)/2$.

 \item $f(q_1) > f(q)/2$. 

Let $q = (a,b)$ with $a > b$. Then $q_1 = (b, a \bmod b)$ and
$q_2 = (a \bmod b, b \bmod a \bmod b)$. Therefore $f(q) = a, f(q_1) = b$
and $f(q_2) = a \bmod b$. We know that $ b > a/2$. Hence $a \bmod b < a/2$.
That is $f(q_2) \leq f(q)/2$.
\end{enumerate}
\qed

\item Let $F_n$ denote the $n^{th}$ Fibonacci number. Show that: 
   \begin{enumerate}
    \item If $2 \leq x \leq F_n$ then the algorithm uses at most 
          $n-2$ modulo operations.

 By Strong Induction.

{\em I. H. } If $2 \leq x \leq F_n$ then the algorithm uses at most 
          $n-2$ modulo operations.

{\em Base. } $x = 3$, $F_4 = 3$. 

{\em Step. }  Assume $P(z)$ for all $z < x$. We will prove $x$.

Suppose $2 \leq x \leq F_n$. Consider the next two transitions.
$$(x,y) \rightarrow (y, x \bmod y) \rightarrow (x \bmod y, y \bmod (x \bmod y))$$
Then $y + x \bmod y \leq x \leq F_n = F_{n-1} + F_{n-2}$.
We consider two cases:
\begin{enumerate}
\item $y \leq F_{n-1}$. 

Then the number of steps is at most 1 + number of steps from the 
state $(y,x \bmod y)$, which is at most $1 + F_{n-3}$ by the 
induction hypothesis applied to $y$.

\item $y > F_{n-2}$. Therefore, $x \bmod y \leq F_{n-2}$. 

The number of steps to termination is at most 2 + number of steps
from the state $(x \bmod y, y \bmod (x \bmod y))$, which is at most 
$2 + n-4 = n-2$ steps by the I.H. applied to $x \bmod y$. 
\end{enumerate}  


    \item For $n \geq 2$, $F_n \geq (\frac{3}{2})^{n-2}$.

By strong induction on $n$.

I.H. $P(n) : F_n \geq (\frac{3}{2})^{n-2}$.

Base: $n=2$: $F_2 = 1 \geq (3/2)^0 = 1$.

Ind. Step: Assume $P(k)$ is true for $2 \leq k \leq n$.
To prove $P(n+1)$. 

$F_{n+1} = F_n + F_{n-1} \geq (\frac{3}{2})^{n-2} + (\frac{3}{2})^{n-3}$

$\geq (\frac{3}{2})^{n-3}(\frac{5}{2}) > (\frac{3}{2})^{n-3} (\frac{3}{2})^2$

$ \geq (\frac{3}{2})^{n-1}$
   
    \item Using the previous two results show that Euclid's algorithm
actually uses at most $1.71 \log_2 x$ modulo operations if $x \geq 2$.


Let $k$ be the smallest integer such that 
$(\frac{3}{2})^{k} \leq x \leq (\frac{3}{2})^{k+1}$
Therefore $x \leq F_{k+3}$, and we know that Euclid's algorithm takes
$k+1$ steps. But this is at most $\log_{3/2} x \leq 1.71 \log_2 x$.

\qed

    \end{enumerate}

\end{enumerate}

  
\item {\em Choosy mating. }
\begin{enumerate}
\item We have the mating problem again, but now both boys and girls are
more choosy about their partners. That is, among a set of $n$ boys
and $n$ girls, each boy is unwilling to 
drop below his $k^{th}$ choice and each girl is unwilliling to below
her $m^{th}$ choice. So it is possible that some of them are not 
married. How many pairs can we be sure of having in general ?


No, in general we cannot guarantee any marriages.
E.g. Let $n = 10, k = m = 5$. $B_1,B_2,..,B_5$ rank only $G_1,\ldots, G_5$,
$B_6,\ldots, B_{10}$ rank only $G_6,..,G_{10}$ and $G_1,\ldots,G_5$ rank
only $B_6,\ldots,B_{10}$ and $G_6,\ldots,G_{10}$ rank only $B_1,\ldots,B_5$.

\item What if only the boys were choosy, i.e., the girls are willing
to marry anyone (they still have a ranked list of preferences), but
the boys will not go below their $k^{th}$ choice?  How many pairs
will the algorithm from class (TMA) assure us?
\end{enumerate}

Set up a state machine as in the lecture. Each state is the set of
ranking lists with names possibly crossed off. Each transition
is one step of the algorithm, i.e. all boys who get a ``no'' answer
cross off the girl who said ``no'' off their lists.

Recall also the derived variables from lecture.

$n(q)$ number of names not crossed off on all the boys lists put together.   

$f_i(q)$ is the rank of girl that boy $i$ is currently pursuing.

$g_i(q)$ is the rank of the boy that girl $i$ said ``maybe'' to.

{\em Termination. }
 $n(q)$ is a decreasing variable. It starts at $nk$ so, the algorithm
terminates in $nk$ steps at most.

{\em At least $k$ marriages. }
$f_i(q)$ is a non-decreasing variable while $g_i(q)$ is a non-increasing 
variable.
If boy $j$ remains unmarried
then $f_j(q) = k+1$. But this means that boy $j$ serenaded all $k$
girls on his list. So at least $k$ girls have $g_i(q) \leq k$.
So they are all definitely married at the end.

{\em No rogue couples. }
Identical to lecture.


Okay, so the TMA guarantees at least $k$ marriages. Is this the best
possible?  Yes, consider e.g., $n = 10, k=5$. For $i = 1$ to $5$
$B_i$ and $G_i$ have each other at the top of their lists. And for
$i = 6$ to $10$, $B_i$ has the list $G_1,..G_5$. So $B_6,..B_{10}$
will stay unmarried as all the girls on their lists have found 
better partners.

\end{enumerate}

\end{document}
