1 files changed, 298 insertions, 0 deletions
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