path: root/howard/hw6.tex

\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