% LaTex2e
\documentclass[12pt]{article}
\usepackage{amssymb,latexsym}

%%%%%%% \usepackage{anysize}
%\marginsize{left}{right}{top}{bottom}
%\marginsize{1.25cm}{1.25cm}{1.75cm}{2.5cm} % this cuts off page numbers
%%%%%% \marginsize{2cm}{2cm}{1cm}{3cm}

\pagestyle{myheadings}
\def\header{{\hfill Exam 2 \hfill A. Miller \hfill Spring 2008
                                       \hfill Math 240\hfill}}
\markboth\header\header

\newcount\probno
\newcount\total
\newwrite\examTBLFile

\probno=0

\def\prob#1{\advance\probno by 1 \par  \vfill \newpage
    \noindent\the\probno . (#1 pts)\advance\total by #1
    \immediate\write\examTBLFile{\the\probno
       \string& #1 \string&
       \string\qquad \string\\ \string\hline}}
\def\probx#1{\advance\probno by 1 \par  \vfill  \newpage
    \noindent\the\probno . (#1 pts)\advance\total by #1
    \immediate\write\examTBLFile{\the\probno
       \string& #1 \string&
       \string\qquad \string\\ \string\hline}}

\def\finishtbl{
    \immediate\write\examTBLFile{Total \string& \the\total
    \string& \qquad \string\\ \string\hline}
     }

\newwrite\ans
\immediate\openout\ans=answers
\outer\def\answer{\par\medbreak
  \immediate\write\ans{}
  \immediate\write\ans{\string\bigskip \the\probno . }
  \copytoblankline}
\outer\def\answerx{\par\medbreak
  \immediate\write\ans{}
  \immediate\write\ans{\string\bigskip \the\probno . }
  \copytoblankline}
\outer\def\putanswer{\par\medbreak
  \immediate\write\ans{}
  \copytoblankline}
\def\copytoblankline{\begingroup\setupcopy\copyans}
\def\setupcopy{\def\do##1{\catcode`##1=12}\dospecials
     \catcode`\|=12\obeylines}
{\obeylines \gdef\copyans#1
  {\def\next{#1}%
  \ifx\next\empty\let\next=\endgroup%
  \else\immediate\write\ans{\next}\let\next=\copyans\fi\next}}
\def\printanswers{\newpage\begin{center} Answers \end{center}
    \immediate\closeout\ans\input answers}

% \def\answer{\par\bigskip\bigskip\bigskip\noindent Answer: \par}
% \outer\def\answer{ {\par\bigskip Circle your answer.} \par\medbreak

\newenvironment{enum}
{\begin{list}{(\alph{enumi})}
{\usecounter{enumi}\setlength{\rightmargin}{\leftmargin}}}
{\end{list}}

\newenvironment{Enum}
{\begin{list}{(\Alph{enumi})}
{\usecounter{enumi}\setlength{\rightmargin}{\leftmargin}}}
{\end{list}}


\def\pow{{\mathcal P}}
\def\sm{\setminus}
\def\su{\subseteq}
\def\nat{{\mathbb N}}
\def\reals{{\mathbb R}}

\begin{document}

\bigskip

\bigskip

No notes, no books, no calculators, no cell phones, no pagers, no
electronic devices of any kind.


\par\vskip .25in
\begin{center}
Name\makebox[3in]{\hrulefill} \\
\end{center}

\bigskip % checked on feb 6
Circle your Discussion Section:
\begin{verbatim}
   DIS 301     9:55        T           B305 VAN VLECK
   DIS 302     9:55        R           115 INGRAHAM
   DIS 305     1:20p       T           B105 VAN VLECK
   DIS 306     1:20p       R           B333 VAN VLECK
\end{verbatim}
\bigskip

\begin{center} \Large
 \begin{tabular}{||c|c|c||} \hline\hline
  Problem & Points & Score \\  \hline\hline
   \input{exam.tbl}
  \hline \hline
 \end{tabular}
\end{center}

\immediate\openout\examTBLFile=exam.tbl

\bigskip

Solutions will be posted shortly after the exam:

www.math.wisc.edu/$\sim$miller/m240

\setcounter{page}{0}

\newpage


\def\ansoh{  \phantom{AAA} $\underline{\phantom{AA}} $\phantom{AAA} }

\prob{12} % 3.2 21
Give the best Big-Oh estimate for each of these functions. Enter
one of the letters  in the blank provided. (Answers may be reused.)
\begin{enumerate}
\item \ansoh   $(2\log(n)+1)(3n+1)$                 
\item \ansoh   $2n\log(n)+n^2$                      
\item \ansoh   $n\log(n^2+n+1)+3n^2\log(n)+ 2n^2$
\item \ansoh   $3\log(n)+5n + 7$                    
\end{enumerate}

\def\bigoh{{\mathcal O}}

\begin{Enum}
\item $\bigoh(n)$
\item $\bigoh(n\log(n))$
\item $\bigoh(n\log^2(n))$
\item $\bigoh(n^2)$
\item $\bigoh(n^2\log(n))$.
\item none of these
\end{Enum}

\answer BDEA


\prob{12} % 4.2 6
\par
(a) Determine which amounts of postage can be formed using 
just 3-cent and 10-cent stamps.
(b) Prove your answer is correct using 
either simple induction or strong
induction.  Be sure to
explicitly state your inductive hypothesis in the inductive step.

\answer (a) 3,6,9,10,12,13,15,16, and all $n\geq 18$.
\par (b) Verify directly that it is true for $n=18,19,20$. 
Prove by strong induction that it is true for every $n> 20$. 
Since if $n> 20$ then $n-3\geq 18$.  Hence by inductive hypothesis
$n-3=\alpha 3+\beta 10$ for some nonnegative integers $\alpha$ and
$\beta$.  But then $n=(\alpha+1)3+\beta 10$.


\def\license#1{Car with license plate starting #1 would park in space 
 \underline{\phantom{AAA}}\phantom{a}.}

\def\xx{30 }

\prob{12} % 3.4 27 
A parking lot has \xx spaces numbered $1,2,\ldots, \xx$
which are assigned by the
hashing function 
$$h(k)=(k \mbox{ mod }\xx)+1$$ 
where $k$ is the integer corresponding
to the first 3 digits on the car's licence plate.
Enter the correct parking space number $1,2,\ldots, \xx$ in each blank:

\bigskip
\begin{enum}
 \item \license{123} 
 \item \license{234} 
 \item \license{432} 
\end{enum}

\answer (a) 4 (b) 25 (c) 13

\prob{12} % 3.5 27 exactly as written
Show that for positive integers $a$ and $b$ that
$$ab=gcd(a,b)\cdot lcm(a,b)$$
Hint: Use the prime factorization of $a$ and $b$ and the
formulas for $gcd(a,b)$ and $lcm(a,b)$ in terms of these
factorizations.

\def\ap{{a^\prime}}
\def\bp{{b^\prime}}

\answer see p.S-21 3.5-27.  \par For another proof:
Let $d=gcd(a,b)$ and $a=\ap \;d$ and $b=\bp \;d$ where
$\ap$ and $\bp$ are relatively prime. Put
$m=\ap \;d\;\bp$.  Then clearly $ab=dm$ and $m$ is a common
multiple of $a$ and $b$.  So it is enough to see that $m$
is the least common multiple.  Suppose $n$ is any common
multiple of $a$ and $b$ and let $n=\alpha a=\beta b$. 
Then since $\alpha \;\ap\; d=\beta \;\bp \;d$ we have that
$\alpha \;\ap =\beta \;\bp $.  Since $\ap$ and $\bp$ are relatively
prime we have that $\ap$ divides $\beta$.  So let
$\beta=\gamma \;\ap$.  But then $n=\beta b=(\gamma \ap)( d\bp)$ and so 
$m=\ap \;d\;\bp$
divides $n$.


\prob{12} % 3.6 17 
Perform the indicated base conversions:
\begin{enum}
\item $(\underline{\phantom{AAAAAAAAA}})_8=(1010111)_2$
\item $(\underline{\phantom{AAAAAAAAA}})_8=(\mbox{E2F})_{16}$
\item $(\underline{\phantom{AAAAAAAAA}})_2=(53)_{10}$
\item $(\underline{\phantom{AAAAAAAAA}})_{10}=(37)_8$
\end{enum}

\answer (a) 127 (b) 7057 (c) 110101 (d) 31 

\prob{12} % 3.7  1 
Using the Euclidean algorithm to express the 
greatest common divisor $d$ of $n=123$ and
$m=1280$ as a
linear combination of $n$ and $m$:
$$d=\alpha (123)+\beta (1280) \mbox{ where $\alpha= \underline{\phantom{AAAA}}$ and 
$\beta= \underline{\phantom{AAAA}}$}.$$

\answer $(32)(1280)+(-333)(123)=1$

\prob{12} % 3.8  5 
Find a matrix $A$ such that
$$
\left[
\begin{array}{cc}
                1 &  2 \\
                2 &  3
\end{array}
\right] A =
\left[
\begin{array}{cc}
                1 &  2 \\
                3 &  4
\end{array}
\right].
$$
Hint: Finding $A$ requires that you solve systems of linear
equations.

\answer $$A =
\left[
\begin{array}{cc}
                3 &  2 \\
                -1 &  0
\end{array}
\right].
$$

\prob{12} % 4.1 15
Prove that for every positive integer $n$:
$$1\cdot 2 \; +\; 2\cdot 3 \; +\;\cdots \;+\; n(n+1)={n(n+1)(n+2)\over 3}$$

\answer see 4.1-15.

\prob{4} % 3.8
True or False.
\begin{enum}
 \item Matrix multiplication satisfies the commutative law.
 \item Matrix multiplication satisfies the associative law.
 \item If $A$ and $B$ are $2\times 2$ matrices and
 $$AB=\left[
\begin{array}{cc}
                0 &  0 \\
                0 &  0
\end{array}
\right]$$
then 
$$A=\left[
\begin{array}{cc}
                0 &  0 \\
                0 &  0
\end{array}
\right]\mbox{ or } 
B=\left[
\begin{array}{cc}
                0 &  0 \\
                0 &  0
\end{array}
\right].$$
 \item For any $n$ there is an $n\times n$ matrix $I$ such that
 for every $n\times n$ matrix $A$
 $$AI=IA=A.$$
\end{enum}

\answer FTFT

\printanswers

\finishtbl

\end{document}



