%%% Fall 2004, HMW 2
\documentclass[11pt]{article}
\usepackage{epsf}
\usepackage{pslatex}
\setlength {\topmargin}{0in}
\setlength {\headheight}{0in}
\setlength {\headsep}{0cm}
\setlength {\textheight}{9in}
\setlength {\oddsidemargin}{0in}
\setlength {\evensidemargin}{0in}
\setlength {\textwidth}{6.5in}
\setlength {\parskip}{0cm}
\setlength{\parskip}{1ex plus 0.5ex minus 0.2ex}
\begin{document}
\thispagestyle{empty}
\begin{center}
{\bf \large ECE G205 Fundamentals of Computer Engineering} \\
{\bf Fall 2003} \\[0.5cm]
{\large \bf Homework 2: Due by Wednesday September 22 2004} \\
\end{center}
{\large
\vspace*{2cm}\noindent
\begin{itemize}
\item This test contains $2$ problems. They allow you to earn
$100$ points.
\item Show your work, as partial credit can be given. You will be
graded not only on the correctness of your answer, but also on the
clarity with which you express it. \textbf{Be neat}.
\item {\bf No late submissions will be accepted.}
\item Only homework returned in a 9in $\times$ 12in envelope
will be accepted. (If you cannot find such envelope, ask the
Instructor.) Please, write your name and the class name (ECE
G205) on the envelope (write clearly, please).
\end{itemize}
\vspace*{3cm}
Write your name here:\
\hrulefill
}
\setcounter{page}{0}
%----------------------------------------------------------------------
\newpage
\begin{itemize}
\item {\bf Problem \# 1\ \ [30 points]}. Consider the \emph{recursive}
implementation of insertion sort seen in class.
\textbf{(a)} Determine the worst case time complexity of
that solution.
\textbf{(b)} Can a function that solves the sorting problem be
written that requires less than $n$ comparisons? ($n$ is the number
of the elements in the array.)
\textbf{(c)} Prove the correctness of your implementation.
%----------------------------------------------------------------------
\newpage
\item {\bf Problem \# 2\ \ [80 points]}. Consider the
problem of determining whether a given integer number $n >
1$ is prime or not. The following simple
algorithm solves the problem (where the C++
operator \texttt{\%} is the modulus operator, which returns the
remainder of the integer division between its operands):
\begin{verbatim}
bool isPrime( int n ) {
bool p = true;
for ( int i = 2; i < n; i++ )
if ( n % i == 0 )
p = false;
return p;
}
\end{verbatim}
\noindent
Function \texttt{isPrime} attempts to divide $n$ by every number $i$ in
the range $2,\ldots,n-1$ and returns \emph{true} only if no number $i$
that divides $n$ has been found.
\noindent
\textbf{(a)} Is this function time complexity polynomial in
the \emph{size of the input}? Justify your answer.
\noindent
\textbf{(b)} Rewrite \texttt{isPrime} by using a
\texttt{while} cycle that terminates as soon as we are sure
that $n$ is not prime. When is it that this implementation
has the same time complexity of the function
\texttt{isPrime} above?
\noindent
\textbf{(c)} Evaluate function \texttt{isPrime} as if it was
executed in a fast computer, that is able to execute
$10^{9}$ operations per second. How long would it take to
check whether an $11$ digit long number is prime? How about
with numbers that are $15$ and $20$ digits long,
respectively? The estimated age of the universe is $5 \times
10^{17}$ years. What kind of number would require at least
that time for checking their primality? Are these uselessly
big numbers, or could they have some practical applications?
\noindent
\textbf{(d)} Consider the following fact: \emph{$n$ is
composite, i.e., it is not a prime number, if and only if
it is divisible by $k \leq \sqrt{n}$.}
Use this fact to write an algorithm for checking whether a
number $n$ is a prime number. Answer part~\textbf{(c)} of
this problem by using your new algorithm.
\end{itemize}
\end{document}