\documentclass[11pt]{article}
\pagestyle{empty}
\newcommand{\sig}{\sigma}
\newcommand{\ra}{\rightarrow}
\newcommand{\eps}{\epsilon}
\newcommand{\gam}{\gamma}
\newcommand{\ah}{\alpha}
\newcommand{\eu}{{\tt EUCLID}}
\newcommand{\eeu}{{\tt EXTENDED-EUCLID}}
\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$}
\\ Solutions
\end{center}
\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$]
\So
\[ \eu(89,55)=\eu(55,34)=\eu(34,21)= \]
\[ =\eu(21,13)=\eu(13,8)=\eu(8,5)= \]
\[ =\eu(5,3)=\eu(3,2)=\eu(2,1)= \]
\[ =\eu(1,0)=1 \]
with all quotients $1$ except the last.
For $\eeu$ we
get a chart like Figure 31.1:
\begin{center}
\begin{tabular}{rrrrrr}
$a$ & $b$ & $\lfloor a/b\rfloor$ & d & x & y \\
\hline
89 & 55 & 1 & 1 & -21 & 34 \\
55 & 34 & 1 & 1 & 13 & -21 \\
34 & 21 & 1 & 1 & -8& 13\\
21 & 13 & 1 & 1 & 5 & -8 \\
13 & 8 & 1 & 1 & -3& 5 \\
8 & 5 & 1 & 1 & 2& -3 \\
5 & 3 & 1 & 1 & -1& 2 \\
3 & 2 & 1 & 1 & 1 & -1 \\
2 & 1 & 2 & 1 & 0 & 1 \\
1 & 0 & - & 1 & 1 & 0 \\
\end{tabular}
\end{center}
so $x=-21$ and $y=34$. (Note that the $x$'s and $y$'s form a
Fibonacci like pattern as well!)
\item Find $\frac{211}{507}$ in $Z_{1000}$.
\So Here we first find $\eu(1000,507)$:
\[ \eu(1000,507)=\eu(507,493)=\eu(493,14)= \]
\[ =\eu(14,3) = \eu(3,2)=\eu(2,1) = \]
\[ = \eu(1,0)=1 \]
For $\eeu$ we
get a chart like Figure 31.1:
\begin{center}
\begin{tabular}{rrrrrr}
$a$ & $b$ & $\lfloor a/b\rfloor$ & d & x & y \\
\hline
1000 & 507 & 1 & 1 & 181 & -357 \\
507 & 493 & 1 & 1 &-176& 181 \\
493 & 14 & 1 &35 & 5&-176\\
14 & 3 & 1 & 4 & -1& 5\\
3 & 2 & 1 & 1 & 1& -1\\
2 & 1 & 1 & 2 & 0& 1\\
1 & 0 & - & 1 & 1& 0 \\
\end{tabular}
\end{center}
so that $1000(181)-357(507)=1$ so in $Z_{1000}$ we
have $(-357)(507)=1$ so $\frac{1}{507}=-357=643$.
Finally $\frac{211}{507}=211\cdot 643=135673=673$.
So the answer is $673$. To check: $673\cdot 507=341211=211$.
\item Solve the system \\ $x\equiv 34 \bmod{101}$\\
$x\equiv 59 \bmod{103}$.
\So We write $x=103y+59$ (we could start with either and this
one is a bit easier) so that in $Z_{101}$ we want
$103y+59=34$ or $2y=-25=76$ and $y=38$. (Usually division is
complicated but here it worked out like normal division.)
Then $x=103(38)+59= 3973$. The general answer is given
as $x\equiv 3973\bmod{10403}$ as $10403=103\cdot 101$.
\item Using the Island-Hopping Method to find $2^{1000}$ modulo
$1001$ using a Calculator but NOT using multiple precision arithmetic.
\So
\[ 2^1 =2 \]
\[ 2^2=2\cdot 2=4 \]
\[ 2^4=4\cdot 4=16 \]
\[ 2^8=16\cdot 16=256 \]
\[ 2^{16}=256\cdot 256 =65536=471 \]
\[ 2^{32}=471\cdot 471 =221841 = 620 \]
\[ 2^{64}=620\cdot 620 =384400 = 16 \]
\[ 2^{128} =16\cdot 16 =256 \]
\[ 2^{256} =256\cdot 256 =65536=471 \]
\[ 2^{512} =471\cdot 471 =221841 = 620 \]
As $1000=512+256+128+64+32+8$ we have
\[ 2^{1000}=620\cdot 471\cdot 256\cdot 16\cdot 620\cdot 256 \]
We calculate in stages:
$620\cdot 471=292020=729$,
$729\cdot 256 = 186624 = 438$,
$438 \cdot 16 = 7008 = 1$,
$1 \cdot 620 = 620 = 620$,
$620 \cdot 256 = 158720 = 562$,
So the answer is $562$. This shows that $1001$ is {\em definitely}
not a prime. (Of course, for numbers this small there are easier ways!)
\item 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$?
\So At that moment $v$ is in a component of size $37$ and it is
the root of the associated tree.
\\
What is the interpretation
of that in the case when $\pi[v]=u\neq v$?
\So $v$ had had size $37$ at the moment when $\pi[v]$ was changed,
and the component with $v$ was joined to the (larger) component with
$u$.
\\ How many different
values can $\pi[w]$ have during the course of Kruskal's
algorithm?
\So Two. Initially $\pi[w]=w$ but once it changes to $\pi[w]=v$ it doesn't change any more.
Precisely one vertex does not ever change, it becomes the root of the final rooted tree.
\\ How many different values (as a function of $V$, the
number of vertices) can $SIZE[w]$ have during the course
of Kruskal's algorithm?
\So $V$. It is possible that $w$ is joined to isolated vertices $V-1$ times and
so $SIZE[w]$ goes from $1$ to $V$ by ones.
\een
\end{document}