\documentclass[11pt]{article}
\pagestyle{empty}
\newcommand{\sig}{\sigma}
\newcommand{\ra}{\rightarrow}
\newcommand{\eps}{\epsilon}
\newcommand{\gam}{\gamma}
\newcommand{\ah}{\alpha}
\newcommand{\ben}{\begin{enumerate}}
\newcommand{\een}{\end{enumerate}}
\newcommand{\hsa}{\hspace*{1cm}}
\newcommand{\hsb}{\hspace*{2cm}}
\newcommand{\So}{\\ {\tt Solution:}}
\begin{document}
\begin{center} {\Large\bf Fundamental Algorithms, Assignment $\omega$}
\\ Due May 7 in Recitation.
\end{center}
{\tt Note:} There will be class Monday, May 11. There will be no
recitation for that class. Problems will be posted but not to
be handed in. The {\bf final exam} is Monday, May 18, 5:10-7 p.m.
in our usual classroom. Info on the final, special office hours,
etc., will be posted on the website.
\begin{quote}
My work has always tried to unite the true with the beautiful and
when I had to choose one or the other I usually chose the beautiful.
-- Hermann Weyl
\end{quote}
\ben
\item Find $d=\gcd(89,55)$ and $x,y$ with $89x+55y=1$. [Remark:
This is part of a pattern with two consecutive numbers from
the Fibonacci sequence $0,1,1,2,3,5,8,13,21,34,55,89,\ldots$]
\item Find $\frac{211}{507}$ in $Z_{1000}$.
\item Solve the system \\ $x\equiv 34 \bmod{101}$\\
$x\equiv 59 \bmod{103}$.
\item Using the Island-Hopping Method to find $2^{1000}$ modulo
$1001$ using a Calculator but NOT using multiple precision arithmetic.
(You should never have an intermediate value more than a million.)
\item (extra from last week!) Suppose that during Kruskal's Algorithm (for MST) and
some point we have $SIZE[v]=37$.
What is the interpretation
of that in the case when $\pi[v]=v$?
What is the interpretation
of that in the case when $\pi[v]=u\neq v$?
Let $w$ be a vertex.
How many different
values can $\pi[w]$ have during the course of Kruskal's
algorithm? How many different values (as a function of $V$, the
number of vertices) can $SIZE[w]$ have during the course
of Kruskal's algorithm? (That is, the maximal number possible.)
\een
\begin{quote}
The universe is not only queerer than we suppose but queerer than we {\em can}
suppose. \\ -- J.B.S. Haldane
\end{quote}
\end{document}