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/hw6.tex | 298 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 298 insertions(+) create mode 100644 howard/hw6.tex (limited to 'howard/hw6.tex') diff --git a/howard/hw6.tex b/howard/hw6.tex new file mode 100644 index 0000000..0d2b4ec --- /dev/null +++ b/howard/hw6.tex @@ -0,0 +1,298 @@ +\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}} + +\li Determine the time complexity of the following algorithm where $n$ +is the input size. Briefly explain how you determined the time +complexity (this does not need to be a proof). + +The time complexity is $O(n\log n).$ The outer loop runs $n$ times and +the inner loop takes $\lfloor \log_5(i) \rfloor$ iterations to complete, +each one in constant time. The total of these is dominated by the $\log +n$ term, giving our time complexity. + +\li Determine the time complexity of the following algorithm where $n$ +is the input size. Briefly explain how you determined the time +complexity (this does not need to be a proof). + +The first loop takes $n$ iterations and the inner part in constant time. +The second loop takes $\log_2(3n)$ iterations, and the sum of these two +is dominated by the higher-order term $O(n).$ + +\li Determine whether 47 divides each of the following numbers. + +{\startlist + +\li 4701 + +No. $4701 = 100\cdot 47 + 1.$ + +\li 94 + +Yes. $94 = 2\cdot 47.$ + +\li 232 + +No. $232 = 5\cdot 47 - 3.$ + +} + +\li Let $a,$ $b,$ and $c$ be integers, where $a\neq 0.$ Use a direct +proof to show that ``if $a\mid b$ and $b\mid c,$ then $a\mid c.$'' You +will need to provide a full proof (introduction, body, and conclusion), +not a ``pseudo-proof'' as seen in lecture. We want you to prove this +theorem, so simply citing Theorem 4.1.1 (iii) will receive no credit. + +{\bf Proof.} + +Let $a,$ $b,$ and $c$ be integers, where $a\neq 0$ such that $a\mid b$ +and $b\mid c.$ +We will show by direct proof that $a\mid c.$ + +From $a\mid b,$ there exists $k\in\bb Z$ such that $b = ak.$ +And from $b\mid c,$ there exists $j\in\bb Z$ such that $c = bj.$ +By substitution, $c = (ak)j = a(jk),$ and $jk\in\bb Z$ by closure of the +integers under multiplication, so $a\mid c$ by definition. + +We have shown that for $a,b,c\in\bb Z$ where $a\neq 0$ and $a\mid b$ and +$b\mid c,$ it must be that $a\mid c.$ +\endproof + +\li Prove that if $a$ is a positive integer, then $4$ does not divide +$a^2+5.$ You will need to provide a full proof (introduction, body, and +conclusion). Hint: it may be helpful to consider different cases for +$a.$ + +{\bf Proof By Contradiction.} + +Let $a$ be a positive integer. +Assume, for the sake of contradiction, that $4$ divides $a^2+5.$ + +Because $a$ is an integer, $a$ is either even or odd. + +Note that this proof uses the fact that $x\mid y$ only if $x\leq0$ or +$y \geq x.$ + +\smallskip +(Even) + +For some $k\in\bb Z,$ $a = 2k,$ so $a^2 = 4k^2,$ and $a^2+5 = 4k^2+5.$ +The assumption $4\mid a^2+5$ tells us that there exists $j\in\bb Z$ such +that $4j = a^2 + 5 = 4k^2 + 5.$ $4(j-k^2-1) = 1$ implies $4\mid 1$ +because $j-k^2-1\in\bb Z$ by closure of the integers under subtraction +and multiplication. This is a contradiction, showing that $4$ doesn't +divide $a^2+5.$ + +\smallskip +(Odd) + +For some $k\in\bb Z,$ $a=2k+1,$ so $a^2 = 4k^2 + 4k + 1,$ and $a^2 + 5 = +4k^2 + 4k + 6.$ +The assumption $4\mid a^2+5$ tells us that there exists $j\in\bb Z$ such +that $4j = a^2 + 5 = 4k^2 + 4k + 6.$ $4(j-k^2-k-1) = 2$ implies $4\mid +2$ because $j-k^2-k-1\in\bb Z$ by closure of the integers under +subtraction and multiplication. +This is a contradiction, showing that $4$ doesn't divide $a^2+5.$ + +\medskip +We have thus shown that for all positive integers $a,$ $4$ does not +divide $a^2+5.$ +\endproof + +\li Suppose that $a$ and $b$ are integers. $a\equiv 7 \pmod{13}$ and +$b\equiv 9 \pmod{13}.$ Find the integer $c$ such that $0\leq c\leq 12$ +in each of the following modular congruences. Note: a calculator is not +needed for these problems, and similar difficulty problems may appear on +the exam (where a calculator is not permitted). + +{\startlist + +\li $c \equiv 12a \pmod{13}$ + +$c\equiv 13-a \equiv 6 \pmod{13}.$ + +$c = 6.$ + +\li $c \equiv 5a + 2b \pmod{13}$ + +$c\equiv 5a + 2(b-13) \equiv 35 - 8 \equiv 1 \pmod{13}.$ + +$c = 1.$ + +\li $c \equiv a^2 + b^3 \pmod{13}$ + +$c\equiv (a-13)^2 + (b-13)^3 \equiv 6^2 - 4^3 \equiv 36 - 64 \equiv -28 +\equiv 11 \pmod{13}.$ + +$c = 11.$ + +\li $c \equiv (2a)^{1000} \pmod{13}$ + +$c\equiv (2a-13)^{1000} \equiv 1^{1000} \equiv 1 \pmod{13}.$ + +$c = 1.$ + +} + +\li Find each of these values. Note: a calculator is not needed for +these problems, and similar difficulty problems may appear on the exam +(where a calculator is not permitted). + +{\startlist + +\li $(18^2 \bmod{9}) \bmod{51}$ + +$18^2 \equiv (18-2\cdot 9)^2 \equiv 0 \pmod{9},$ giving us $0.$ + +\li $(7^2 \bmod{23})^3 \bmod{8}$ + +$7^2 \equiv 49-46 \equiv 3 \pmod{23},$ and $3^3 \equiv 27 - 24 \equiv 3 +\pmod{8},$ giving us $3.$ + +\li $(5^4 \bmod{11})^4 \bmod{6}$ + +$5^2 \equiv 3 \pmod{11},$ so $5^4 \equiv (5^2)^2 \equiv 3^2 \equiv 9 +\pmod{11}.$ + +$9^4 \equiv 3^4 \equiv 3 \pmod{6},$ giving us $3.$ + +} + +\li Convert the decimal expansion of each of these integers into a +binary expansion. Show your work for full credit. + +{\startlist + +\li 323 + +We start from $323$ and subtract one if odd then divide by two, +prepending a one if odd and a zero otherwise. + +We start by subtracting one and diving by two to get $1_2$ and $161.$ + +Then we have $11_2$ and $80.$ + +Then $011_2$ and $40.$ + +Then $0011_2$ and $20.$ + +Then $00011_2$ and $10.$ + +Then $000011_2$ and $5.$ + +Then $1000011_2$ and $2.$ + +Then $01000011_2$ and $1.$ + +Then $(1\,0100\,0011)_2,$ and we've completed our algorithm. + +\li 234 + +We start from $234$ and subtract one if odd then divide by two, +prepending a one if odd and a zero otherwise. + +We start by dividing by two to get $0_2$ and $117.$ + +Then we have $10_2$ and $58.$ + +Then we have $010_2$ and $29.$ + +Then we have $1010_2$ and $14.$ + +Then we have $01010_2$ and $7.$ + +Then we have $101010_2$ and $3.$ + +Then we have $1101010_2$ and $1.$ + +Then we have $(1110\,1010)_2$ and we've completed our algorithm. + +\li 52 + +We start from $52$ and subtract one if odd then divide by two, +prepending a one if odd and a zero otherwise. + +We start by dividing by two to get $0_2$ and $26.$ + +Then we have $00_2$ and $13.$ + +Then we have $100_2$ and $6.$ + +Then we have $0100_2$ and $3.$ + +Then we have $10100_2$ and $1.$ + +Then we have $(11\,0100)_2$ and we've completed our algorithm. + +} + +\li Convert the binary expansion of each of these integers into a +decimal and octal expansion. Show your work for full credit. + +{\startlist + +\li $(101\,1111)_2$ + +For the decimal expansion, I computed $1\cdot 2^6 + 1\cdot 2^4 + 1\cdot +2^3 + 1\cdot 2^2 + 1\cdot 2^1 + 1\cdot 2^0 = 64+16+8+4+2+1 = 95.$ + +For the octal expansion, we group it into triplets and then convert each +segment. $111_2 = 7_8,$ $011_2 = 3_8,$ and $1_2 = 1_8,$ giving expansion +$(137)_8.$ + +\li $(1011\,0101)_2$ + +Again, for the decimal expansion, we compute $1\cdot 2^7 + 1\cdot 2^5 + +1\cdot 2^4 + 1\cdot 2^2 + 1 \cdot 2^0 = 128 + 32 + 16 + 4 + 1 = 181.$ + +And for the octal expansion, we group it into triplets again, starting +from the end, $101_2 = 5_8,$ $110_2 = 6_8,$ and $10_2 = 2_8,$ giving +expansion $(265)_8$ + +} + +\li Convert $(A6CD1)_{16}$ from its hexadecimal expansion into a binary +expansion. Show your work for full credit. + +We convert each nibble into its corresponding binary expansion. $A_{16} += 1010_2,$ $6_{16} = 0110_2,$ $C_{16} = 1100_2,$ $D_{16} = 1101_2,$ and +$1_{16} = 0001_2,$ so we get the full expansion +$(1010\,0110\,1100\,1101\,0001)_2.$ + +\li Convert $(1001\,0110\,1010\,0001\,0110)_2$ from its binary expansion +into a hexadecimal expansion. Show your work for full credit. + +We convert each nibble into its corresponding hexadecimal character. +$1001_2 = 9_{16},$ $0110_2 = 6_{16},$ $1010_2 = A_{16},$ $0001_2 = +1_{16},$ and $0110_2 = 6_{16},$ giving us hexadecimal expansion +$(96A16)_{16}.$ + +\bye -- cgit