\documentclass[11pt]{article}
\usepackage{header}
%%% Change these %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\def
\title{HW 4}
\def
\due{Friday, September 23 at 10PM}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{document}
\maketitle
\fontsize{12}{15}
\selectfont
\begin{Questions}
\Question{\bf Sundry}
Before you start your homework, write down your team. Who else did you work with on this homework? List names and email addresses. (In case of hw party, you can also just describe the group.) How did you work on this homework? Working in groups of 3-5 will earn credit for your "Sundry" grade.
Please copy the following statement and sign next to it:
\textit{I certify that all solutions are entirely in my words and that I have not looked at another student's solutions. I have credited all external sources in this write up.}
%%% Include questions here %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Question (32 points)
\textbf{Modular Arithmetic}
Solve the following equations for $x$ and $y$
modulo the indicated modulus, or show that no
solution exists. Show your work.
\begin{enumerate}
\item (8 points) $9x
\equiv 1
\pmod{11}
$.
% 1/9 = -1/2 = -6 = 5
\item (8 points) $10x+23
\equiv 3
\pmod{31}
$.
% 1/10 = -3 = 28
\item (8 points) $3x+15
\equiv 4
\pmod{21}
$.
% no solution
\item (8 points) The system of simultaneous equations
$3x+2y
\equiv 0
\pmod7$ and $2x+y
\equiv 4
\pmod7$.
% x = 1, y = 2
\end{enumerate}
\Question (8 points)
\textbf{Don't Try This at Home}
A ticket in the lottery consists of six numbers chosen from $1,2,
\ldots,48$
(repetitions allowed). After everyone has bought their tickets, the
manager picks 5 winning numbers from this set at random. Your ticket
wins if it contains each of these winning numbers. Order is
irrelevant.
Prove that if you buy all possible tickets for which the sum of the
six entries on the ticket is divisible by 47, then you are guaranteed
to have a winner.
\newcommand{\etc}{{\textit{etc.}}\/}
\newcommand{\ie}{{\textit{i.e.}}\/}
\newcommand{\ignore}[1]{}
\Question (50 points)
\textbf{Further extending the extended GCD algorithm}
In class, you learned how to use Euclid's algorithm to find the GCD of $2$
numbers $x$ and $y$. You also saw an extended version of the algorithm that
allowed you to find $2$ other numbers $a$ and $b$ such that $ax + by =
\textnormal{GCD}
(x,y)$.
In this problem, you're going to analyze an algorithm that finds the GCD of
\textit{more than}
$2$ numbers. That is, you're given $n$ numbers $
[x_{1},\x_{2},\\ldots,\{n} x_]
$, and your job is to develop/analyze an algorithm that
finds the greatest natural number (the GCD) that divides all the given numbers.
\begin{Parts}
\Part[x_{1},\{2} x_,\\ldots,\{n} x_] (10 points) Suppose you're given $n$ non-negative numbers $
$, at least one of which is strictly positive. Of these $n$
numbers, let $z$ be the smallest number that is strictly positive. Before going
ahead, convince yourself that such a $z$ exists.
Now, suppose I take each number $x_
{i}
\neq z$ on the list above, and
replace it with the remainder that I get when I divide $x_
{i}
$ by $z$. Let's say
this results in a new list $
[y_{1},\{2} y_,\\ldots,\{n} y_]
$. Show that:
$$
\textnormal{GCD}
(x_
{1}
,
\{2} x_
,
\
\ldots,
\{n} x_
) =
\textnormal{GCD}
(y_
{1}
,
\{2} y_
,
\
\ldots,
\{n} y_
).$$
\Part (10 points) Consider the algorithm
\texttt{GCDmany}
below that is intended to compute the GCD of a list of numbers.
\texttt{
\mbox{~} \textbf{algorithm} GCDmany (list [$x_{1}$, $x_{2}$, $\ldots$,{n} $x_$]):\\
\mbox{~ ~ ~} nz = list of all non-zero elements of $[x_{1},\{2} x_,\\ldots,\{n} x_]$\\
\mbox{~ ~ ~} \textbf{if} length(nz) == 1:\\
\mbox{~ ~ ~ ~ ~} \textbf{return} nz[0] $\quad$\textit{\# the first and only element of nz}\\
\mbox{~ ~ ~} [idx, m] = min(nz) $\ $\textit{\# position, value of smallest element of nz}\\
\mbox{~ ~ ~} \textbf{foreach} $k\neq\texttt{idx}$ such that $0 \leq k < \texttt{length(nz)}$:\\
\mbox{~ ~ ~ ~ ~} nz[k] = nz[k] mod m\\
\mbox{~ ~ ~} \textbf{return} GCDmany(nz)
}
Using the result that you proved in Part 1, show that the
\texttt{GCDmany}
algorithm correctly returns the GCD of any list of non-negative numbers,
provided that at least one of the numbers in the list is strictly positive.
\Part (10 points) Suppose I run the
\texttt{GCDmany}
algorithm on $n$ positive
numbers, each represented by $m$ bits. Derive a bound (in terms of $m$ and $n$)
for the number of recursion calls that the algorithm execution will result in.
\Part (10 points) Suppose I tell you the following:
\begin{itemize}
\item{Listing all non-zero elements given $n$ $m$-bit numbers can be done in at most $mn$ computer operations,}
\item{Computing the minimum of $n$ $m$-bit numbers can be done using at most $4mn$ operations,}
\item{The remainder on dividing one $m$-bit number by another can be calculated within $3m^{2}$ operations,}
\item{All other steps needed by the \texttt{GCDmany} algorithm take at most $10$ computer operations, and}
\item{Each computer operation takes $1ns$ on my computer.}
\end{itemize}
Based on the above, derive an upper bound for how long it will take for
my computer to find the GCD of $100$ positive $64$-bit numbers using the
\texttt{GCDmany}
algorithm above.
\Part (10 points) Suppose I'm interested in computing not just the GCD $G$ of the
$n$ positive numbers $x_
{1}
$ to $x_
{n}
$, but also integer coefficients $a_
{1}
$
to $a_
{n}
$ such that:
$$
\sum_{i=1}
^
{n}
a_
{i}
x_
{i}
= G.$$
Describe how you will modify the
\texttt{GCDmany}
algorithm to also output the
coefficients above. Write down the steps in your modified algorithm in a format
similar to the
\texttt{GCDmany}
algorithm above.
\end{Parts}
\Question (Optional)
\textbf{The last digit}
\\
Let $a$ be a positive integer. Consider the following sequence of numbers
$x$ defined by:
\begin{eqnarray*}
x_0 &=& a \\
x_
{n}
&=& x_
{n-1}
^2 + x_
{n-1}
+ 1
\text{ if }
n > 0
\end{eqnarray*}
\begin{Parts}
\Part Show that if the last digit of $a$ is 3 or 7, then for every $n$,
the last digit of $x_n$ is respectively 3 or 7.
\Part Show that there exist $k > 0$ such that the last digit of $x_n$ for
$n
\geq k$ is constant. Give the smallest possible $k$,
\textit{no matter what}
$a$ is.\\
\end{Parts}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\end{Questions}
\end{document}