\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 $11$}
\\ Due Dec 5 in Recitation.
\end{center}
\begin{quote}
...pleasure has probably been the main goal all along.
But I hesitate to admit it, because computer scientists want to
mantain their image as hard-working individuals who deserve high
salaries. Sooner or later society will realise that certain kinds of
hard work are in fact admirable even though they are more fun than
just about anything else.
\\ -- Don Knuth
\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 possible number
of different values.)
\een
\begin{quote}
A foolish consistency is the hobgoblin of little minds, adored by
little statesman and philosophers and divines. With consistency a
great soul has simply nothing to do.
\\ -- Ralph Waldo Emerson
\end{quote}
\end{document}