From 8dafd8aec819e85fd36cbd1d6231aad24e62c31b Mon Sep 17 00:00:00 2001 From: Holden Rohrer Date: Tue, 16 Aug 2022 18:21:57 -0400 Subject: Finished work from last semester --- howard/hw5.tex | 222 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 222 insertions(+) create mode 100644 howard/hw5.tex (limited to 'howard/hw5.tex') 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 -- cgit