1 files changed, 222 insertions, 0 deletions
diff --git a/howard/hw5.tex b/howard/hw5.tex
new file mode 100644
index 0000000..e7d8cef
--- /dev/null
+++ b/howard/hw5.tex
@@ -0,0 +1,222 @@
+\newfam\bbold
+\def\bb#1{{\fam\bbold #1}}
+\font\bbten=msbm10
+\font\bbsev=msbm7
+\font\bbfiv=msbm5
+\textfont\bbold=\bbten
+\scriptfont\bbold=\bbsev
+\scriptscriptfont\bbold=\bbfiv
+
+\newcount\indentlevel
+\newcount\itno
+\def\reset{\itno=1}\reset
+\def\afterstartlist{\advance\leftskip by .5in\par\advance\leftskip by -.5in}
+\def\startlist{\par\advance\indentlevel by 1\advance\leftskip by .5in\reset
+\aftergroup\afterstartlist}
+\def\alph#1{\ifcase #1\or a\or b\or c\or d\or e\or f\or g\or h\or
+    i\or j\or k\or l\or m\or n\or o\or p\or q\or r\or
+    s\or t\or u\or v\or w\or x\or y\or z\fi}
+\def\li#1\par{\medskip\penalty-100\item{\ifcase\indentlevel \number\itno.\or
+                                  \alph\itno)\else
+                                  (\number\itno)\fi
+                           }%
+         #1\smallskip\advance\itno by 1\relax}
+\def\ul{\bgroup\def\li##1\par{\item{$\bullet$} ##1\par}}
+\let\endul\egroup
+\def\hline{\noalign{\hrule}}
+\let\impl\rightarrow
+\newskip\tableskip
+\tableskip=10pt plus 10pt
+\def\endproof{\leavevmode\quad\vrule height 6pt width 6pt
+depth 0pt\hskip\parfillskip\hbox{}{\parfillskip0pt\medskip}}
+
+\def\oldcomma{,}
+\catcode`\,=13
+\def,{%
+    \ifmmode
+        \oldcomma\mskip\medmuskip\discretionary{}{}{}%
+    \else
+        \oldcomma
+    \fi
+}
+
+\li For each of the following functions, determine $f: \bb Z \times \bb
+Z \to \bb Z,$ determine whether the function is:
+
+\item{i)} onto and one-to-one
+
+\item{ii)} onto but not one-to-one
+
+\item{iii)} not onto but one-to-one
+
+\item{iv)} neither onto nor one-to-one
+
+\item{v)} not a function
+
+{\startlist
+
+\li $f(x,y) = 3x^2-2y.$
+
+Neither onto nor one-to-one.
+$1$ is unreachable, and $f(1,0) = f(-1,0).$
+
+\li $f(x,y) = y! + x.$
+
+Not a function. $y!$ is not defined on $y<0.$
+
+\li $f(x,y) = 2x\cdot 3y.$
+
+Neither onto nor one-to-one.
+$1$ is unreachable, but $f(0,1) = f(1,0).$
+
+\li $f(x,y) = x - y.$
+
+Onto but not one-to-one
+All integers are reachable, but $f(0,0) = f(1,1).$
+
+\li $f(x,y) = |x| + y.$
+
+Onto but not one-to-one
+All integers are reachable, but $f(0,1) = f(1,0).$
+}
+
+\li Use the cashier's algorithm to make change using quarters, dimes,
+nickels, and pennies for the following amounts of money. You do not have
+to specifically show how you greedily formed change, but rather there
+are many ways to make this change and only the cashier's/greedy
+distribution will be accepted.
+
+{\startlist
+
+\li 43 cents
+
+One quarter, a dime, a nickel, 3 pennies
+
+\li 68 cents
+
+Two quarters, a dime, a nickel, 3 pennies.
+
+\li 98 cents
+
+Three quarters, two dimes, 3 pennies
+}
+
+\li Imagine that a new coin that is worth exactly 4 cents has been
+introduced to our existing currency system.  Prove or disprove the
+statement: ``The cashier’s algorithm using quarters, dimes, nickels,
+4-cent coins, and pennies and will always produce change using the
+fewest coins possible.''
+
+This is false. 8 cents is decomposed into 1 nickel and 3 pennies by the
+greedy algorithm, but is decomposed as 2 4-coins, which is fewer coins.
+
+\li State whether the following is True or False and explain your
+reasoning for full credit:
+
+{\startlist
+
+\li Given two integers $x$ and $c,$ if $x+c < 10,$ then $\lfloor x/10
+\rfloor = \lfloor (x+c)/10 \rfloor.$
+
+False. For $x = 0$ and $c=-100,$ then $x+c < 10$ but $\lfloor
+x/10\rfloor = 0 \neq -10 = \lfloor (x+c)/10\rfloor.$
+
+\li Given two functions $f(x)$ and $g(x),$ if $f(g(x))$ is defined, then
+$g(f(x))$ must also be defined.
+
+False. Let $f: \bb N \to \bb R$ and $g: \bb N \to \bb N.$
+$f\circ g: \bb N \to \bb R,$ but $g\circ f$ undefined.
+}
+
+\li For each of these function from $\bb R^+ \to \bb R,$ find the least
+integer $n$ such that $f(x)$ is $O(x^n)$ if possible. If not, explain
+why the function cannot be $O(x^n).$
+
+{\startlist
+
+\li $f(x) = x^2\sqrt x.$
+
+This function is $O(x^3).$ $x \geq \sqrt x,$ and the product of
+$O(f(x))$ and $O(g(x))$ is $O(f(x)g(x)).$
+
+\li $f(x) = 2x^3 + x^2\log(3x)$
+
+This function is $O(x^3).$ All polynomials are $O(x^n)$ where $n$ is the
+highest degree in the polynomial.
+
+\li $f(x) = {x^5 + x^4 \over x^4 + 5\log_5(5^x)}$
+
+This function is $O(x).$ ($n=1$)
+The top polynomial is $O(x^5)$ because polynomials are on the order of
+their highest degree, and the bottom polynomial is $x^4 + 5x = O(x^4).$
+A rational function $g/h$ is on the order of $O(g)/O(h),$ so $f = O(x).$
+
+\li $f(x) = \log(1000)$
+
+This function is $O(1).$ ($n=0$) Any constant is $O(1).$
+
+\li $f(x) = {3^x\over x^3} + {x^3\over\log(x)}$
+
+This function is not $O(x^n)$ for any $n.$
+The exponential function grows faster than any polynomial function.
+}
+
+\li Consider the linear search algorithm as outlined in class. How many
+values would 15 be compared to in the sequence $(1,7,13,22,44,15,7,9).$
+
+It would be compared to 6 values and on the last comparison, 15 is
+found and the algorithm exits.
+
+\li Consider the binary search algorithm as outlined in class. (You must
+use this exact version of the binary search algorithm):
+
+{\startlist
+
+\li List the values that 44 would be compared to in a search for 44 in
+the following sequence: $(1,7,9,13,15,44,57,88).$ Make sure to include
+the final value in the ``equality'' check as well.
+
+We will examine $(13, 44, 15, 44),$ the 4th, 6th, and 5th elements until
+$i=j=6,$ and we exit the loop and check we have the right element.
+
+\li List the values that 103 would be compared to in a search for 103 in
+the following sequence: $(3,8,17,21,44,73,88,101,113).$ Make sure to
+include the final value in the ``equality'' check as well.
+
+We examine $(44, 88, 101, 113),$ the 5th, 7th, and 8th elements until
+$i=j=9,$ and we check $x = a_9$ and find that our number is not in the
+list.
+}
+
+\li Prove or disprove the following statements.
+
+{\startlist
+
+\li $\lfloor 2x \rfloor = \lfloor x \rfloor + \lfloor x + 0.5 \rfloor,$
+for all $x\in\bb R.$
+
+{\bf Proof.}
+
+Let $x\in\bb R.$
+$x$ can be uniquely represented as $n+r$ where $0\leq r < 1,$ and
+$n\in\bb Z.$
+
+If $r < 1/2,$ $\lfloor x \rfloor = \lfloor x + 0.5 \rfloor = n.$
+$2x = 2n + 2r,$ and $0\leq 2r < 1,$ so $\lfloor 2x \rfloor = 2n =
+\lfloor x \rfloor + \lfloor x + 0.5 \rfloor.$
+
+If $r\geq1/2,$ $\lfloor x \rfloor = n$ and $\lfloor x+0.5 \rfloor =
+n+1.$ $2x = 2n + 1 + 2(r-1/2)$ and $0 \leq r-1/2 < 1,$ so $\lfloor 2x
+\rfloor = 2n+1,$ so $\lfloor x \rfloor + \lfloor x + 0.5 \rfloor.$
+
+\li $x^3 + x^2 + \log(x)$ is $O(x^3).$ (If you choose to prove this
+statement you must do so using witnesses).
+
+{\bf Proof.}
+
+On $x \geq 1,$
+$x^3 \geq x^3,$ $x^3 \geq x^2,$ and $x^3 \geq \log x,$ so
+$3x^3 \geq x^3 + x^2 + \log x$ for $x \geq 1,$ so we know that $x^3 +
+x^2 + \log(x) = O(x^3).$
+
+\bye