\documentclass [12pt] {article}

\usepackage{graphicx, amsmath, amssymb}
\usepackage{algorithm2e}
\DeclareGraphicsRule{.tif}{png}{.png}{`convert #1 `dirname #1`/`basename #1 .tif`.png}


\topmargin 0pt
\advance \topmargin by -\headheight
\advance \topmargin by -\headsep
\textheight 8.9in
\oddsidemargin 0pt
\evensidemargin \oddsidemargin
\marginparwidth 0.5in
\textwidth 6.5in

\begin{document}
\begin{center}
\begin{tabular*}{6in}{c@{\extracolsep{\fill}}c@{\extracolsep{\fill}}c}
  EXAM 2 &\huge TCSS 321  &\normalsize Fall 2012\\
\end{tabular*}
\end{center}
\vskip .1 in

\begin{enumerate}
\item $[6]$ TRUE/FALSE: Circle T in each of the following cases if the 
statement is \emph{always} true and briefly justify your answer.  Otherwise, circle F and provide a counterexample or brief reasoning.  

\begin{tabular}{lll}
~\\
T &F & Binary search can locate a specified element, if it exists, in an arbitrary sequence.\\
~\\
~\\
~\\
T &F &  If $ac\equiv bc \mod m$, where $a$, $b$, $c$, and $m$ are integers with $m\geq 2$, \\
&&then $a\equiv b \mod m$.\\
~\\
~\\
~\\
T &F & There are a countable infinite number of primes.\\
~\\
~\\
~\\
\end{tabular}
\vskip .2 in
\large
\noindent{Show your work for the following problems.  The correct answer with 
no supporting work will receive NO credit.}

\normalsize
\item $[2]$ What's your favorite algorithm? Why?
\vspace{1in}
\item $[4]$ (\S4.3 \#31) The product of two integers is $2^5\cdot3^8\cdot 5^3\cdot 7^{11}$ and their greatest common divisor is $2\cdot 3^7 \cdot 7^9$.  What is their least common multiple? Show your work or your reasoning.

\newpage

\item Consider the Sort algorithm described below for the next three questions.

\begin{algorithm}[H]
% \SetAlgoLined
 \KwData{$a_0$, $a_1$, ... $a_{n-1}$: integers where $n>2$}
 \KwResult{integers sorted in increasing order }
 %initialization\;
 \For{$i=0$ to $n-1$}{
  	smallSub=i\;
  	\For{$j=i$ to $n-1$}{
		  \If{$a_j<a_{\text{smallSub}}$}{
   		smallSub=j\;
		   }
		   temp =$a_i$\;
		   $a_i=a_{\text{smallSub}}$\;
		   $a_{\text{smallSub}}=$temp\;
  }
 }
 \caption{Sort Algorithm}
\end{algorithm}

\begin{enumerate}
\item $[4]$ (Quiz3 \#4) List the steps used by the Sort algorithm on the input $\{7,6,8,5\}$.  Clearly indicate when and what swaps/recordings/interchanges are made.
\vspace{2.0in}
\item $[2]$ Describe the Sort algorithm as you would to a colleague during lunch.
\vspace{1in}
\item $[2]$ (\S3.3 \#3) Give a big-O estimate for the comparisons used in the sort algorithm.  Show your reasoning.
\vspace{1in}
\end{enumerate}

\newpage

\item Each of the following give an exact count of operations taken in a worse case senerio for a certain algorithm.  Identify their complexity (big-O for programmers or big-$\Theta$ for computer scientists) as you would to a colleague and justify yourself.
\begin{enumerate}
\item $[2]$ (\S3.2 \#6) $\displaystyle{\frac{x^3+2x}{2x+1}}$
\vspace{.7in}
\item $[2]$ (\S3.2 \#7b) $4x^3+(\log x)^4$
\vspace{.7in}
\item $[2]$ (\S3.2 \#19) $2^{x+1}+8x^{15}$
\vspace{.7in}
\end{enumerate}



\item $[5]$ Choose \emph{ONE} of the following and support your conclusions.  Clearly identify which of the two you are answering and what work you want to be considered for credit.  \\
\begin{enumerate}
\item (\S3.1 \#23) Clearly describe an algorithm that determine whether a function from a finite set of integers to another finite set of integers is onto.  Specifically the inputs are: $f$:function, $[x_0,x_1,...x_n]$:integers in domain, $[y_0,y_1,...y_m]$: integers in codomain.
\item (\S3.1 \#32) Clearly describe and algorithm that finds all terms of a finite sequence of integers that are greater then the sum of all previous terms in sequence. 
\end{enumerate}




\newpage

\item 
\begin{enumerate}
\item $[3]$ (\S4.2 \#21) Find $10011_2+10110_2$
\vspace{1in}
\item $[2]$ (\S4.2 \#3) Convert the binary number $10110_2$ into decimal.
\vspace{1in}
\item $[3]$ (\S4.2 \#40) Recall the two's complement representation of an integer:  

To represent an integer $x$ between $2^{n-1}\leq x \leq 2^{n-1}$ using $n$ bits we use the leftmost bit to record the `sign'.  A $0$ bit in this position is used for a positive integer and a $1$ bit in this position is used for a negative integer.  For a positive integer, the remaining bits are identical to the binary expansion of the integer.  For a negative integer, the remaining bits are the bits of the binary expansion of $2^{n-1}-|x|$.

Find the 6 bit two's complement to $-21$.
\vspace{1in}

\item $[2]$ (\S4.2 \#3) Consider the answer to (c) as only a binary number (as opposed to a two's complement representation).  Convert the above binary number into decimal.
\vspace{1in} 

\item $[3]$ (\S4.1 \#13) Find $c$ such that $c+21\equiv 0 \text{ mod } 32$.
\vspace{1in}

\item $[Extra Credit]$ Identify how the two's complement representation with $6$ bits is related to arithmetic modulo $2^6$ or $\mathbb{Z}_{32}$.
\end{enumerate}


\newpage
\item $[6]$ Choose \emph{ONE} of the following and support your conclusions.  Clearly identify which of the two you are answering and what work you want to be considered for credit.  \\
\begin{enumerate}
\item (\S4.1 \#7) Prove if $a$, $b$, and $c$ are positive integers where $a\not=0$ and $c\not=0$ such that $(ac)\vert (bc)$ then $a \vert b$.

\item (Lecture 11/5) Prove if $a$, $b$, and $c$ are positive integers such that $\gcd(a,b)=1$ and $a \vert (bc)$, then $a \vert c$.
\end{enumerate}


%\includegraphics[height=1.7in]{exam1d}
%$g(x)= \begin{cases}
%\hspace{1in} 			& \text{if $-2\leq x \leq 1$}\\
 %	& \text{if $2\leq x\leq 6$}\\


\end{enumerate}

\end{document}
