\magnification\magstep3
\input /profs/cs1/kaltofen/text/def.tex
\hoffset=-0.5truein \hsize=7.4truein
\tenpoint
\hbox to \hsize {\hbox to 0cm{{\bf Comput.\ Abstract Algebra}\hss}\hfill
{\sl First Mid-Semester Exam}\hfill
\hbox to 0cm {\hss{\rm Spring 1990}}}
\vskip 0.5truecm
\par\noindent{\sl Your Name:} \hbox to 5cm{\hrulefill}
\vskip 0.5truecm
This examination consists of 4 questions, each question counting for the 
given number of points, adding to a total of 20 points. Write your answers
on these pages (using the back of the sheets if necessary)
following the problems.
There is also an extra page at the end of the exam.
You are allowed to consult your notes or the textbook.
If you get stuck on a problem, go to another
one. You will only have $75$ minutes to do this test, so budget your time
carefully.\hfill Good Luck!
\vskip 1truecm
$$\vbox{\halign{\hfill#\hskip 0.25cm&#\hbox to 1cm{\hrulefill}\cr
Problem 1&\cr
2&\cr
3&\cr
4&\cr
\omit\cr
Total&\cr}}$$
\vfill\eject
\noindent{\bf Problem 1} (4 points):
Consider the following program for computing $a^n$:
\smallskip
\verbatim|
     {n a non-negative integer}
     X := a; Y:= 1; k := n;
     while (k > 0) do
        begin if odd(k)
                 then begin Y := X * Y; k := (k-1)/2 end
                 else k := k/2;
              X := X * X
        end
     {Y = a**n}|
\medskip\noindent
Prove that when the while loop is terminated, variable {\tt Y}
contains the value of $a^n$.
[Hint: ($a^n={\tt Y} \times {\tt X}^{\hbox{\tt k}}$ and ${\tt k} \ge 0$) is a loop invariant.]
\vfill\eject\noindent
\noindent{\bf Problem 2} (6 points):
Let $f_n$ be the $n$-th Fibonacci number, namely,
$$f_0 = 0, f_1 = 1, f_{i+2} = f_{i+1}+f_{i}
                       \hbox{ for all }i \ge 0.$$
\item{(a)}
Show by induction on $n$ that $\GCD(f_n, f_{n+1})=1$
for all $n \ge 0$.
\vskip12truecm
\item{(b)}
When computing the GCD of $f_n$ and $f_{n+1}$ using the Euclidean
algorithm with division with positive remainder, how many
divisions are performed to obtain the GCD (which is~1)?
\vfill\eject\noindent
{\bf Problem~2} continued:
\item{(c)}
Using the extended Euclidean algorithm with
division that leaves the absolute smallest remainder,
compute $g=\GCD(f_9, f_8)$ and $s, t\in \ZZ$ such that
$g = s f_9 + t f_8$.
\vskip 14truecm
\item{\null}
{\bf Bonus question:} Generalizing from (c), how many divisions are performed
when applying the Euclidean algorithm to $f_n$ and $f_{n+1}$
using division that leaves absolutely smallest remainder?
\vfill\eject\noindent
{\bf Problem 3} (5 points):
Consider the following subset of the complex numbers,
$${\cal O}_{-2}=\{a + \sqrt{-2}\,b \mid a, b\in \ZZ\}.$$
${\cal O}_{-2}$ is an integral domain with respect to complex
number addition and multiplication.
\item{(a)}
Which elements are units in ${\cal O}_{-2}$?
Describe a canonical simplifier for association in ${\cal O}_{-2}$.
\vskip 8truecm
\item{(b)}
For $\alpha=a +\sqrt{-2}\,b\in {\cal O}_{-2}$
the function $\delta(\alpha)=| \alpha |^2=a^2+2 b^2$ is a Euclidean
degree function. Given $\alpha, \beta\in {\cal O}_{-2}$, $\beta \not= 0$,
show how to compute $\gamma, \rho\in {\cal O}_{-2}$ such that
$\alpha = \gamma \beta + \rho$ and $\delta(\rho)<\delta(\beta)$. 
\vfill\eject\noindent
{\bf Problem 4} (5 points): The following two parts are
unrelated.
\item{(a)}
There are two kinds of randomized algorithms, {\it Las Vegas} (will
always compute the correct answer, but the running time is subject
to having luck in the coin tosses) and {\it Monte Carlo} (will always
run efficiently, but the correctness of the answer is subject
to having luck in the coin tosses).
The Pollard-$\rho$ integer factoring method is a Monte Carlo
method. Explain why. Given that only composite numbers are
fed to the method, can it be modified to become a Las Vegas algorithm?
\vskip 10truecm\noindent
\item{(b)}
Consider a ring $R$ and an ideal $I \subset R$. Does the set
$I$ using addition and multiplication from $R$
form a ring itself? Explain your answer.
\vfill\eject
Extra space for answers.
\bye