\documentstyle[12pt,twoside]{article}

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

\raggedbottom

\input{macros-course}

\iffalse
\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{corollary}[theorem]{Corollary}
\newcommand{\qed}{\mbox{\ \ \ }\rule{6pt}{7pt} \bigskip}
\fi
%\newtheorem{fact}{Fact}
\begin{document}

\handout{teamprobs4}{Problems for Recitation 4}{October 2, 1998}


\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]

\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.

    \item For $n \geq 2$, $F_n \geq (\frac{3}{2})^{n-2}$.
   
    \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$.
    \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 ?

\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}

\end{enumerate}

 
\end{document}

