% 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}


\def\reals{{\mathbb R}}
\def\integers{{\mathbb Z}}
\def\naturals{{\mathbb N}}

\pagestyle{myheadings}
\def\header{{\hfill Final Exam \hfill A. Miller \hfill Spring 2005
                                       \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\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

\begin{document}

\bigskip

Show all work.

% Simplify your answers.

% Circle your answer.

\bigskip

No books, no calculators, no cell phones, no pagers, no
electronic devices of any kind.
However you can bring to the exam 
   one  $8.5$ by $11$
cheat sheet with anything you want written or printed on both sides.

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

\bigskip
Circle your Discussion Section:
\begin{verbatim}

    DIS 303 12:05p T B235 VAN VLECK
    DIS 304 12:05p R B235 VAN VLECK
    DIS 307  2:25p T B139 VAN VLECK
    DIS 308  2:25p R B309 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


\prob{10} % 2.3-17  (did problem 1.8-17 instead)
Give examples of functions from the set of
integers, 
$$\integers=\{0,1,-1,2,-2,3,-3,\ldots\},$$ 
to the set of natural numbers,
$$\naturals=\{1,2,3,\ldots\},$$ 
having the given properties.

\bigskip (a) $f:\integers\to \naturals$ such that 
$f$ is one-to-one and onto.

\def\myskip{\vskip 1.8in}

\myskip
 (b) $g:\integers\to \naturals$ such that $g$ is onto, but not one-to-one.

\myskip
 (c) $h:\integers\to \naturals$ such that $h$ is one-to-one, but not onto.

\myskip
 (d) $k:\integers\to \naturals$ such that $k$ is neither one-to-one 
nor onto.

\prob{10} % 2.5- 3
Convert the integer $1 1111 0101$ from binary notation (base 2)
to:

\bigskip (a) hexadecimal notation (base 16)

\myskip (b) octal notation (base 8)
 
\myskip (c) decimal notation  (base 10)



\prob{10} % 2.7-31
In this problem matrix operations are
done using the bit operations $\vee$ and $\wedge$ instead
of $+$ and $\cdot$.

$$A=\left[
\begin{array}{rrr}
 1  &  0  & 0 \\
 1  &  0  & 1 \\
 0  &  1  & 0 \\
\end{array}\right]$$

\bigskip 
(a) Find $A^{[2]}$

\def\myskip{\vskip 2in}

\myskip
(b) $A^{[3]}$

\myskip
(c) $A\vee A^{[2]}\vee A^{[3]}$


\prob{10} % 3.1-41
Given an integer $a_n$ if $a_n$ is even let $a_{n+1}=a_n/2$, if
$a_n$ is odd let $a_{n+1}=3a_n+1$.  The $3x+1$ conjecture states that
given any positive integer $a_0$ there exists an integer $n\geq 0$ 
such that $a_n=1$.  Prove that this conjecture is true for $a_0=17$.

\prob{10} % 3.2-33
If $A$ is an uncountable set and $B$ is a countable set, must
$A\setminus B$ be uncountable?  Prove it.

\prob{10} % 3.4-41
For $w$ a string
of symbols and $i$ a positive integer let $w^i$ represent the concatenation of
$i$ copies of $w$.
Prove using mathematical induction that $len(w^i)=i\cdot len(w)$ where
$len(w)$ stands for the length of $w$.

\answer Base: $len(w^1)=len(w)=1\cdot len(w)$
\par Inductive step: Assume $len(w^i)=i\cdot len(w)$.  Then
\par $len(w^{i+1})=len(w^{i}w)=len(w^i)+len(w)=i\cdot len(w)+len(w)
=(i+1)\cdot len(w)$

\prob{10} % 4.3-15
In how many ways can a set of four letters be selected from the 
English alphabet assuming the following: 

\def\myskip{\vskip 1.2in}

\bigskip
(a)  They are distinct and the order in
which you select them counts.

\myskip
(b)  They are distinct but the order in which you 
select them does not count.

\myskip
(c)  They may not be distinct but the order in 
which you select them counts.

\myskip
(d)  They may not be distinct and the order in which
you select them does not count.

\answer (a) $26\cdot 25\cdot 24\cdot 23$ (b) $C(26,4)$ (c) $26^4$
(d) $C(29,4)$

\prob{10} % 7.3-27  too much work to draw graph - so I reversed it
Draw a digraph which represents the binary relation:
$$R=\{(a,a),(b,b),(d,d),(a,b),(b,c), (c,a),(a,c)\}$$

\prob{10} % 7.5-11
(a) Let the relation $R$ on the set $D$ of all differentiable
functions from $\reals$ to $\reals$ consist of all pairs
$(f,g)$ such that $f^\prime(x)=g^\prime(x)$
for all real numbers $x$.  Prove that
$(D,R)$ is an equivalence relation.

\vskip 5in

\par (b) Which functions are in the same equivalence class as
the function $$f(x)={x^3\over 3}$$


\answer (b) $\{{x^3\over 3}+C\;\; :\;\; C\in\reals\}$

\prob{10} % 9.1- 5  - did 11 instead - too hard to draw pictures.
How many rooted trees are there with the three vertices $\{a,b,c\}$? 
Draw them.                                                           

\answer 9

\finishtbl

\newpage

The following program was used to pick the problems on the test.
I changed a few and dropped two. For example,
instead of 2.3-17 I used problem 1.8-17.


\begin{verbatim}
#! /usr/ucb/python

import string
import sys
import random
random.seed("Harpo, Groucho, and Chico")

f=open("hmwk1",'r')    # input file
lines=f.readlines()
lines=lines[19:]
problems=[]
for line in lines:
  s=string.split(line)
  if len(s)>0:
    section=s.pop(0)
    prob=random.choice(s)
    problems.append(section+"-"+prob.rjust(2))

f=open("hmwk2",'r')    # input file
lines=f.readlines()
lines=lines[32:]
for line in lines:
  s=string.split(line)
  if len(s)>0:
    section=s.pop(0)
    prob=random.choice(s)
    problems.append(section+"-"+prob.rjust(2))
random.shuffle(problems)
test=problems[0:8]

f=open("hmwk3",'r')    # input file
lines=f.readlines()
lines=lines[28:]
problems=[]
for line in lines:
  s=string.split(line)
  if len(s)>0:
    section=s.pop(0)
    prob=random.choice(s)
    problems.append(section+"-"+prob.rjust(2))

random.shuffle(problems)
problems=problems[0:4]

for prob in problems:
 test.append(prob)
test.sort()
 
for prob in test:
  print prob

               OUTPUT:

               2.3-17
               2.5- 3
               2.7-31
               3.1-41
               3.2-33
               3.4-41
               3.6- 5
               4.3-15
               7.3-27
               7.5-11
               7.6-53
               9.1- 5



\end{verbatim}


\printanswers

\end{document}



