aboutsummaryrefslogtreecommitdiff
path: root/howard
diff options
context:
space:
mode:
authorHolden Rohrer <hr@hrhr.dev>2022-08-16 18:21:57 -0400
committerHolden Rohrer <hr@hrhr.dev>2022-08-16 18:21:57 -0400
commit8dafd8aec819e85fd36cbd1d6231aad24e62c31b (patch)
tree42885fc08fffcb3fb74fa9a0f9e1ee5bd7a30045 /howard
parent621cd1d1112e7fa88a5319a65070981e4918d3c8 (diff)
Finished work from last semesterHEADmaster
Diffstat (limited to 'howard')
-rw-r--r--howard/Makefile2
-rw-r--r--howard/hw10.tex379
-rw-r--r--howard/hw11.tex236
-rw-r--r--howard/hw5.tex222
-rw-r--r--howard/hw6.tex298
-rw-r--r--howard/hw7.tex192
-rw-r--r--howard/hw8.tex115
-rw-r--r--howard/hw9.tex144
8 files changed, 1587 insertions, 1 deletions
diff --git a/howard/Makefile b/howard/Makefile
index 7685eb6..31bfdc1 100644
--- a/howard/Makefile
+++ b/howard/Makefile
@@ -6,7 +6,7 @@ PDFTEX = pdftex
.tex.pdf:
$(PDFTEX) $<
-all: hw1.pdf hw2.pdf hw3.pdf hw4.pdf
+all: hw1.pdf hw2.pdf hw3.pdf hw4.pdf hw5.pdf hw6.pdf hw7.pdf hw8.pdf hw9.pdf
clean:
rm -f *.pdf *.log
diff --git a/howard/hw10.tex b/howard/hw10.tex
new file mode 100644
index 0000000..01b8a46
--- /dev/null
+++ b/howard/hw10.tex
@@ -0,0 +1,379 @@
+\input tikz
+
+\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\nmid{\hskip-3pt\not\hskip2.5pt\mid}
+
+\li Given that $f(n)$ is a function for all non-negative integers $n,$
+find $f(2),$ $f(3),$ and $f(4)$ for each of the following recursive
+definitions:
+
+{\startlist
+
+\li $f(0) = 1$
+
+$f(n+1) = 2f(n)^2+2$
+\smallskip
+$f(2) = 34$
+
+$f(3) = 2314$
+
+$f(4) = 10,709,194.$
+
+\li $f(0) = 5$
+
+$f(1) = 4$
+
+$f(n+1) = (3*f(n)) \bmod{(f(n-1)+1)}$
+\smallskip
+$f(2) = 0$
+
+$f(3) = 0$
+
+$f(4) = 0$
+
+\li $f(0) = 1$
+
+$f(n+1) = 2^{f(n)}$
+\smallskip
+$f(2) = 4$
+
+$f(3) = 16$
+
+$f(4) = 65536$
+
+\li $f(0) = 1$
+
+$f(1) = 3$
+
+$f(n+1) = f(n) - f(n-1)$
+\smallskip
+$f(2) = 2$
+
+$f(3) = -1$
+
+$f(4) = -3$
+
+\li $f(0) = 2$
+
+$f(n+1) = (n+1)^{f(n)}$
+\smallskip
+$f(2) = 2$
+
+$f(3) = 9$
+
+$f(4) = 4^9 = 262,144.$
+}
+
+\li Recursively define the following sets.
+
+{\startlist
+
+\li The set of all positive powers of 3 (i.e. 3, 9, 27, \dots)
+
+$3\in S.$
+
+If $x,y\in S,$ then $xy\in S.$
+
+\li The set of all bitstrings that have an even number of 1s
+
+$0\in S.$
+
+If $\gamma\in S,$ then $0\gamma,\gamma0,1\gamma1\in S.$
+
+\li The set of all positive integers $n$ such that $n\equiv 3\pmod{7}$
+
+$3\in S.$
+
+If $x\in S,$ then $7+x\in S.$
+
+}
+
+\li Recursively define the following sequences, where $n\in\bb Z^+$
+
+{\startlist
+
+\li $a_n = 2n!$
+
+$a_1 = 2.$ $a_n = na_{n-1}.$
+
+\li $a_n = n*(5^n)$
+
+$a_1 = 5.$ $a_{n+1} = {n+1\over n}5a_n.$
+
+}
+
+\li Recursively define the function $\rm CS(x)$ that takes in a string
+of uppercase letters and finds the sum of the number of C's and the
+number of S's in the string. For example, ${\rm CS(`SOCKS')} = 3$
+because SOCKS has two S's and one C.
+
+$CS('') = 0$
+
+$CS(S\lambda) = 1+CS(\lambda).$
+
+$CS(C\lambda) = 1+CS(\lambda).$
+
+And, where $l$ is any letter other than $C$ or $S,$
+$CS(l\lambda) = CS(\lambda).$
+
+
+\li Use a tree diagram to find the number of bit strings of length four
+that do not contain three consecutive zeros.
+
+\tikzpicture
+[
+ level 1/.style = {sibling distance = 8.5cm},
+ level 2/.style = {sibling distance = 4.5cm},
+ level 3/.style = {sibling distance = 2.5cm},
+ level 4/.style = {sibling distance = 1cm},
+]
+\node {}
+ child {node {0}
+ child {node {00}
+ child {node {001}
+ child {node {0010}}
+ child {node {0011}}
+ }
+ }
+ child {node {01}
+ child {node {010}
+ child {node {0100}}
+ child {node {0101}}
+ }
+ child {node {011}
+ child {node {0110}}
+ child {node {0111}}
+ }
+ }
+ }
+ child {node {1}
+ child {node {10}
+ child {node {100}
+ child {node {1001}}
+ }
+ child {node {101}
+ child {node {1010}}
+ child {node {1011}}
+ }
+ }
+ child {node {11}
+ child {node {110}
+ child {node {1100}}
+ child {node {1101}}
+ }
+ child {node {111}
+ child {node {1110}}
+ child {node {1111}}
+ }
+ }
+ };
+\endtikzpicture
+
+There are 13 bit strings.
+
+\li Use a tree diagram to determine the number of ways to arrange the
+letters a, b, c, and d such that c comes before b.
+
+\tikzpicture
+[
+ level 1/.style = {sibling distance = 4.5cm},
+ level 2/.style = {sibling distance = 2cm},
+ level 3/.style = {sibling distance = 1cm},
+]
+\node {}
+ child {node {a}
+ child {node {ac}
+ child {node {acb}
+ child {node {acbd}}
+ }
+ child {node {acd}
+ child {node {acdb}}
+ }
+ }
+ child {node {ad}
+ child {node {adc}
+ child {node {adcb}}
+ }
+ }
+ }
+ child {node {c}
+ child {node {ca}
+ child {node {cab}
+ child {node {cabd}}
+ }
+ child {node {cad}
+ child {node {cadb}}
+ }
+ }
+ child {node {cb}
+ child {node {cba}
+ child {node {cbad}}
+ }
+ child {node {cbd}
+ child {node {cbda}}
+ }
+ }
+ child {node {cd}
+ child {node {cda}
+ child {node {cdab}}
+ }
+ child {node {cdb}
+ child {node {cdba}}
+ }
+ }
+ }
+ child {node {d}
+ child {node {da}
+ child {node {dac}
+ child {node {dacb}}
+ }
+ }
+ child {node {dc}
+ child {node {dca}
+ child {node {dcab}}
+ }
+ child {node {dcb}
+ child {node {dcba}}
+ }
+ }
+ };
+\endtikzpicture
+
+There are 12 ways to arrange these such that c comes before b.
+
+\li How many integers from 1 to 1000:
+
+{\startlist
+
+\li Are divisible by 7?
+
+$$\lfloor {1000\over 7}\rfloor = 142.$$
+
+\li Are divisible by 7 but not 11?
+
+$$\lfloor {1000\over 7}\rfloor - \lfloor{1000\over 77}\rfloor = 130.$$
+
+\li Are divisible by exactly one of 7 and 11?
+
+$$\lfloor {1000\over 7}\rfloor + \lfloor{1000\over 11}\rfloor -
+2\lfloor{1000\over 77}\rfloor = 208.$$
+
+\li Are divisible by neither 7 nor 11?
+
+$$1000 - \lfloor{1000\over 7}\rfloor - \lfloor{1000\over 11}\rfloor +
+\lfloor{1000\over 77}\rfloor = 780.$$
+
+\li Have distinct digits?
+
+Treating the three-, two-, and one-digit cases separately, and then
+evaluating all choices of digits which don't start with 0 gives:
+$$9\cdot9\cdot 8 + 9\cdot 9 + 9 = 738.$$
+
+\li Have distinct digits and are even?
+
+In the one digit case, we have $\{2,4,6,8\},$ so four numbers.
+
+In the two digit case, we have one of the 9 numbers ending in zero, or
+we have one of the 8 distinct-digit numbers for each other even digit,
+giving $32+9=41$ amounts.
+
+In the three digit case, we can take the two-digit numbers and insert
+one of the remaining 8 digits into the middle,
+giving $41\cdot 8 = 328$ numbers.
+
+Adding these up, we get $373$ even numbers with distinct digits between
+1 and 1000.
+}
+
+\li A password name is a string between 1 and 4 characters (inclusive),
+and it can consist of lowercase letters, uppercase letters, digits,
+dollar signs, or underscores. However, the first character cannot be a
+digit, and if the first character is either a dollar sign or an
+underscore, then all other characters must be digits. How many different
+password names exist under these rules?
+
+% backus-naur form
+% L = [a-Z] 52
+% D = [0-9] 10
+% C = [_$] 2
+% * = L | D | C
+% P = C[D[D[D]]] | L[*[*[*]]]
+% 2 * (1 + 10 * (1 + 10 * (1 + 10)))
+%+52 * (1 + 64 * (1 + 64 * (1 + 64)))
+
+There are 52 letters, 10 digits, and 2 special characters.
+Dividing the set into two classes (starting with letters and starting
+with special characters), we can then compute the choice of ending the
+password (1 option) or adding another digit/letter (10 or 52 times the
+number of combinations remaining)
+
+This gives us the combinatorial expression
+$$2 * (1 + 10 * (1 + 10 * (1 + 10))) + 52 * (1 + 64 * (1 + 64 * (1+64)))
+= 13,850,082.$$
+
+\li Assume that a website only allows strings of length 5 as a username
+for a user account. Valid characters for a username consist of lowercase
+letters, uppercase letters, digits, or underscores, and they have the
+following requirements:
+
+\ul
+
+\li If the username begins with a vowel, then it must end with 2 even
+digits.
+
+\li If the username begins with a consonant, then the remaining four
+characters must also be letters.
+
+\endul
+
+How many different usernames exist under the given constraints?
+
+% V = 10
+% C = 42
+% L = 52
+% E = 5
+% O = 11
+% * = 63
+% V**EE | CLLLL | O****
+
+There are three different patterns.
+The first is a vowel, 2 of any character, and 2 even digits, giving us
+$10*63^2*5^2$ options.
+The second is a consonant and four letters, gviing
+$42*52^4$ options.
+The third is a digit or underscore and four of any character, giving
+$11*63^4$ characters.
+
+The total number of options is $481,362,693.$
+
+\bye
diff --git a/howard/hw11.tex b/howard/hw11.tex
new file mode 100644
index 0000000..ec30878
--- /dev/null
+++ b/howard/hw11.tex
@@ -0,0 +1,236 @@
+\input tikz
+
+\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\nmid{\hskip-3pt\not\hskip2.5pt\mid}
+
+\li How many numbers must be selected from the set
+$\{1,4,6,8,9,13,14,16,18,21\}$ to guarantee that at least one pair of
+these numbers adds up to exactly 22? Simplify your answer to an integer.
+
+6 numbers must be selected. This set has five pairs that sum to 22, so
+we're putting 6 pigeons into 5 holes, which guarantees one pair is
+completed, and we get a sum to 22.
+
+\li How many different combinations of pennies, nickels, dimes, and
+quarters can a piggy bank contain if it has 29 coins in it? Simplify
+your answer to an integer.
+
+This is 29 coins into 4 categories, so
+$${29+4-1\choose 3} = 4960$$
+different possibilities for the coins in this piggy bank.
+
+\li How many different ways are there to choose 13 donuts if the shop
+offers 19 different varieties to choose from? Simplify your answer to an
+integer.
+
+This is equivalent to putting 13 indistinct balls into 19 urns, which by
+stars and bars is
+$${19+13-1\choose 13-1} = 141,\!120,\!525$$
+different choices.
+
+\li Imagine you are drawing cards from a standard deck of 52 cards. For
+each of the following, determine the minimum number of cards you must
+draw from the deck to guarantee that those cards have been drawn.
+Simplify all your answers to integers.
+
+{\startlist
+\li A Straight (5 cards of sequential rank). Hint: when considering the
+Ace, a straight could be A, 2, 3, 4, 5 or 10, J, Q, K, A, but no other
+wrap around is allowed.
+
+We must eliminate the 5 and the 10 to prevent us from getting a
+straight, so the highest number we can get before we get a straight is
+$(13-2)\cdot 4 = 44$ and we need 45 cards to guarantee us a straight.
+
+\li A Flush (5 cards of the same suit)
+
+We have 4 holes and we want to guarantee 5 cards in a hole, so by
+generalized pigeonhole, we need $4\cdot 4+1 = 17$ cards.
+
+\li A Full House (3 cards of 1 rank and 2 from a different rank)
+
+We have thirteen holes (ranks) and we want 3 pigeons in a hole, so
+generalized pigeonhole gives us $13\cdot 2 + 1 = 27$ cards.
+
+\li A Straight Flush (5 cards of sequential rank from the same suit)
+
+Once we are guaranteed a straight by part (a), we must have a straight
+flush since we already have most of the other cards in the same suit.
+Therefore, 45 cards guarantees us a straight flush.
+}
+
+\li How many integers between 1 and 1000 meet the criteria below.
+Simplify your answer to an integer.
+
+\ul
+
+\li the digits are distinct
+
+\li the digits are odd
+
+\li the digits are in ascending order
+
+\endul
+
+We start from the set of odd digits $\{1,3,5,7,9\},$ complete the
+picking process for one-, two-, and three-digits, and then reorder in
+ascending order.
+This gives us
+${5\choose 3} + {5\choose 2} + {5\choose 1} = 25$
+different numbers.
+
+\li How many teenagers (people from age 13--19) must you select to
+ensure that 4 of theme were born on the exact same date (mm/dd/yyyy)?
+Simplify your answer to an integer.
+
+We will use the generalized pigeonhole principle.
+This 7 year period includes either one or two leap years.
+If it includes one leap year, this is $7\cdot 365 + 1$ days and we will
+need $3\cdot(7\cdot 365 + 1) + 1$ teenagers to ensure 4 with the same
+birth date.
+
+\li A coin is flipped 10 times. Simplify your answers to integers.
+
+{\startlist
+
+\li How many possible outcomes are there?
+
+$$2^{10} = 1024.$$
+
+\li How many possible outcomes are there where the coin lands on heads
+at most 3 times?
+
+We treat the 0 heads, 1 head, 2 heads, and 3 heads cases:
+$${10\choose 0} + {10\choose 1} + {10\choose 2} + {10\choose 3} = 176.$$
+
+\li How many possible outcomes are there where the coin lands on heads
+more than it lands on tails?
+
+We treat the 0 tails, 1 tails, 2 tails, 3 tails, and 4 tails cases:
+$${10\choose 0} + {10\choose 1} + {10\choose 2} + {10\choose 3} +
+{10\choose 4} = 386.$$
+
+\li How many possible outcomes are there where the coin lands on heads
+and tails an equal number of times?
+
+$${10\choose 5} = 252.$$
+
+}
+
+\li How many solutions are there to the following equations? Simplify
+your answer to an integer.
+
+{\startlist
+
+\li $a_1 + a_2 + a_3 + a_4 = 100$
+
+where $a_1,$ $a_2,$ $a_3,$ and $a_4$ are positive integers?
+
+We can compute this using stars and bars, giving 99 spots and 3 bars or
+$${99\choose 3} = 156,\!849$$
+solutions to the equation.
+
+\li $a_1 + a_2 + a_3 + a_4 + a_5 = 100$
+
+where $a_1,$ $a_2,$ $a_3,$ $a_4,$ and $a_5$ are non-negative integers,
+and $a_1 > 5.$
+
+First we subtract 5 from both sides and then add 4 to both sides to
+change the bounds on all of our numbers to $a_k > 0.$
+We would then have $\sum = 101.$
+Using stars and bars, we will obtain
+$${100\choose 4} = 3,\!921,\!225$$
+solutions to this equation.
+
+\li $a_1 + a_2 + a_3 = 100$
+
+where $a_1,$ $a_2,$ and $a_3$ are non-negative integers, and $a_3\leq
+10.$
+
+Computing ignoring the restriction, we get ${102\choose 2}$ solutions.
+Then we consider the ones that violate the restriction ($a_3\geq11$) as
+${91\choose 2}$ solutions.
+The number of solutions following the restriction is
+$${102\choose 2} - {91\choose 2} = 1056.$$
+
+}
+
+\li How many different strings can be created by rearranging the letters
+in ``addressee''? Simplify your answer to an integer.
+
+There are
+$${9\choose 1,2,3,2,1} = 15,\!120$$
+strings (random permutation of 9 characters and then discount the
+positioning of the 2 d's, the 3 e's, and the 2 s's)
+
+\li Let a class consist of 8 CS major students and 8 CM major students.
+Each student is either a CS major or a CM major, but not both. How many
+distinct ways are there to arrange the students in a line such that no
+student stands next to someone in the same major as themselves? Simplify
+your answer to an integer.
+
+There are two ways to do this (assuming indistinct students), either
+starting with a CS or CM major.
+Then the internal order of each major is $8!,$ giving us, for distinct
+students,
+$$2\cdot 8! \cdot 8! = 3,\!251,\!404,\!800$$
+ways to arrange them.
+
+\li Three pairs of twins are sharing a bucket of 24 chicken wings from
+Olive Oyl's. Through the magic of twinship, each person always eats
+exactly as many chicken wings as their twin. If each person eats at
+least one chicken wing, how many ways can the chicken wings be
+distributed amongst the people? For the purposes of this problem,
+chicken wings are indistinguishable, and every chicken wing is eaten.
+Simplify your answer to an integer.
+
+This is equivalent to three people sharing a bucket of 12 chicken wings.
+Using stars and bars, we get
+$${11\choose 2} = 55$$
+ways to eat the chicken wings.
+
+\li CS 2050 has 10 recitation sections. 7 of the recitation sections are
+led by a pair of TAs, and 3 recitation sections are led by a trio of
+TAs. How many ways are there to line up the TAs such that each TA is
+standing next to their recitation partner(s)? Simplify your answer to an
+integer.
+
+First, we consider how many ways we can arrange the recitation sections
+($10!$).
+Then we determine how many ways each recitation can be internally
+arranged in the line ($(3!)^3\cdot(2!)^7$)
+This computes to
+$$10!\cdot(3!)^3\cdot(2!)^7 = 100,\!329,\!062,\!400$$
+ways to arrange the TAs.
+
+\bye
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
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
diff --git a/howard/hw7.tex b/howard/hw7.tex
new file mode 100644
index 0000000..39d2f64
--- /dev/null
+++ b/howard/hw7.tex
@@ -0,0 +1,192 @@
+\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\lcm{\mathop{\rm lcm}}
+
+\li Find the prime factorization of each of these integers.
+
+{\startlist
+
+\li 9072
+
+$9072 = 2^4\cdot 3^4\cdot 7.$
+
+\li 324
+
+$324 = 2^2\cdot 3^4.$
+
+\li 6!
+
+$6! = 2^4\cdot 3^2\cdot 5.$
+
+}
+
+\li Approximate the number of prime numbers not exceeding 50000. Show
+your work.
+
+The approximate number of primes less than $N$ is $N/\ln(N)$
+$${50000\over\ln(50000)} \approx {50000\over 10.82} \approx 4621.$$
+
+\li Determine whether the integers 2, 51, 101, and 119 are pairwise
+relatively prime. Show your work for full credit.
+
+These are the prime factorizations of the above numbers:
+
+$2 = 2.$
+
+$51 = 3\cdot 17.$
+
+$101 = 101.$
+
+$119 = 7\cdot 17.$
+
+$51$ and $119$ are not coprime because they share the factor 17.
+Every other pair is relatively prime.
+
+\li What is the greatest common divisors of these pairs of integers?
+
+{\startlist
+
+\li $2^4*3^3*5^6$ and $2^5*3^3*5^2*7^2.$
+
+$2^4*3^3*5^2.$
+
+\li 19 and $19^1 8.$
+
+19.
+}
+
+\li What is the least common multiple of these pairs of integers?
+
+{\startlist
+
+\li $2^4*3^3*5^6$ and $2^5*3^3*5^2*7^2.$
+
+$2^5*3^3*5^6*7^2.$
+
+\li $2^4*7$ and $5^5*13.$
+
+$2^4*5^5*7*13.$
+
+}
+
+\li Find the least integer with $n$ distinct positive factors where $n$
+is below. For example, if $n=4,$ then the solution is $6$ because
+$1,2,3,6$ are distinct positive factors of $6$ and there are $n=4$ of
+them.
+
+{\startlist
+
+\li 3
+
+$4$ has factors $1,2,4.$
+
+\li 5
+
+$16$ has factors $1,2,4,8,16.$
+
+\li 6
+
+$12$ has factors $1,2,3,4,6,12.$
+
+}
+
+\li Use the Euclidean algorithm to find the following values. You must
+clearly show all steps of your work using the Euclidean algorithm taught
+in class.
+
+{\startlist
+
+\li $\gcd(100,101)$
+
+$(100,101)\to (100, 1)\to (1, 0),$ giving $\gcd(100,101) = 1.$
+
+\li $\gcd(64, 12)$
+
+$(64, 12)\to (12, 4)\to (4, 0),$ giving $\gcd(64,12) = 4.$
+
+}
+
+\li Show your work by using the Chinese Remainder Theorem, find all
+values $x$ such that
+
+$x \equiv 1 \pmod{5}.$
+
+$x \equiv 2 \pmod{6}.$
+
+$x \equiv 3 \pmod{7}.$
+
+\smallskip
+5, 6, and 7 are pairwise coprime, so these congruences specify a unique
+integer $n$ such that $x\equiv n \pmod{210}.$
+
+$y_1 = 42,$ and $a_1 = 1,$ so $z_1 = 3.$
+
+$y_2 = 35,$ and $a_2 = 2,$ so $z_2 = 5.$
+
+$y_3 = 30,$ and $a_3 = 3,$ so $z_3 = 4.$
+
+$a_1y_1z_1 + a_2y_2z_2 + a_3y_3z_3 \equiv 206 \bmod{210}.$
+
+\li Decrypt the following ciphertext message: $HJUXDW,$ which was
+encrypted first using a shift cipher, then using a transposition cipher.
+The key of the shift cipher was $k=3,$ and the transposition cipher was
+based on the permutation $\sigma$ of the set 1, 2, 3 with $\sigma(1) =
+2$ and $\sigma(2) = 3$ and $\sigma(3) = 1.$
+
+We start by computing a transposition $\sigma^{-1}(3) = 2$ and
+$\sigma^{-1}(2) = 1$ and $\sigma^{-1}(1) = 3.$
+The ciphertext becomes $JUHDWX.$
+We then convert the ciphertext to numbers
+$(9, 20, 7, 3, 22, 23)$ and subtract three to get
+$(6, 17, 4, 0, 19, 20),$ and finally convert numbers to letters,
+obtaining $GREATU.$
+
+\li Suppose you intercept the message ``57 04 00 59 50 57 04 14 52 50 57
+42 00 54'' that has been encrypted using the RSA algorithm. You know
+that the public key used for encryption is $(65,7).$ Decrypt the message
+to determine what was said. Use the process shown in lecture to complete
+this problem. You must show all work. (If your calculator is unable to
+calculate $a^d\bmod{n}$ where a is one of the numbers in the message above and
+$d$ is the decryption key, then you can just show $a^d\bmod{n}$ for each value of
+a. Note that this is the final step in decryption so you won't show what
+the message actually was. You must still show the work for calculating
+the decryption key $d$).
+
+$n = 13\cdot 5 = p\cdot q.$
+$\lcm(p-1,q-1) = 12.$
+$7\cdot 7 \equiv 1 \pmod{12},$
+so $d = 7$ (the multiplicative inverse of 7 mod 12)
+
+We then compute $a^d\bmod{n}$ for each number in the message, obtaining
+$(8,4,0,19,15,8,4,14,13,15,8,3,0,24)$ or $IEATPIEONPIDAY.$
+
+\bye
diff --git a/howard/hw8.tex b/howard/hw8.tex
new file mode 100644
index 0000000..c760b02
--- /dev/null
+++ b/howard/hw8.tex
@@ -0,0 +1,115 @@
+\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\lcm{\mathop{\rm lcm}}
+
+\li Use mathematical induction to prove that the following statement is
+true for all positive integers $n.$
+
+$$8+15+22+29+\ldots+(7n+1) = {(7n(n+1)+2n)\over 2}.$$
+
+We start with the base case $n = 1.$
+$$8 = {7(1)(1+1)+2(1)\over 2} = {14+2\over 2} = 8.$$
+
+We now inductively assume that the statement is true for some positive
+integer $k,$ and prove the statement for $k+1.$
+
+$$8+15+\ldots+(7k+1) = {7k(k+1)+2k\over 2}.$$
+
+We add $7(k+1)+1$ to both sides.
+$$8+15+\ldots+(7k+1)+(7(k+1)+1) = {7k(k+1)+2k\over 2} + 7(k+1)+1 =$$$$
+{7k(k+1) + 7(2)(k+1) + 2k + 2\over 2} = {7(k+1)(k+2) + 2(k+1)\over 2}.$$
+
+We have thus shown the statement for $k+1.$
+
+By mathematical induction, we have proven the initial statement for all
+positive integers $n.$
+
+\li Use mathematical induction to prove or disprove that the following
+statement is true for all non-negative integers $n.$
+
+$$1+nh \leq (1+h)^n,\hbox{ where }h>-1.$$
+
+We start with the base case of the smallest non-negative integer $n=0.$
+$$1+0h = 1 \leq 1 = (1+h)^0,$$
+(note that $h>-1,$ so $(1+h)>0,$ so $(1+h)^0 = 1.$)
+
+We now assume that the statement is true for some non-negative integer
+$k$ and prove the statement for $k+1.$
+
+We know the inductive hypothesis $1+kh \leq (1+h)^k$ and multiply both
+sides by $1+h$ to get
+$(1+kh)(1+h) = 1+(k+1)h+kh^2 \leq (1+h)^{k+1}$
+$0\leq h^2,$ so $0\leq kh^2,$ so $1+(k+1)h \leq (1+h)^{k+1}.$
+
+By mathematical induction, we have shown that for all non-negative
+integers $n,$ $1+nh \leq (1+h)^n.$
+
+\li Use mathematical induction to prove or disprove that the following
+statement is true for all positive odd integers $n.$
+
+$$n^2-1\hbox{ is divisible by }8.$$
+
+We start with the base case of the smallest positive odd integer $n=1.$
+$n^2-1 = 1-1 = 0,$ and $8\mid 0,$ showing our base case.
+
+We now assume that the statement is true for some positive odd integer
+$k.$ Because $k$ is odd, there is an integer $j$ such that $k = 2j+1.$
+We start from the inductive hypothesis $k^2-1$ is divisible by 8, so
+there is an $l$ such that $k^2-1 = 8l.$
+$$k^2-1 = (2j+1)^2-1 = 4j^2+4j.$$
+We add $8j+8$ to both sides.
+$$4j^2+12j+8=(2j+3)^2-1 = (k+1)^2-1 = 8(l+j+1),$$
+showing that $(k+1)^2-1$ is divisible by 8.
+
+By mathematical induction, we have now shown that, for all positive odd
+integers $n,$ $n^2-1$ is divisible by 8.
+
+\li Use mathematical induction to prove that the following statement is
+true for all integers $n$ greater than 1.
+
+$$n! < n^n.$$
+
+We start with the base case $n = 2.$ $2! = 2 < 4 = 2^2.$
+
+We now inductively assume the statement is true for some $k \geq 2,$ and
+we show that $(k+1)! < (k+1)^{k+1}.$
+
+Noting that $k^k < (k+1)^k$ for $k > 1,$
+$$k! < k^k < (k+1)^k.$$
+
+We then multiply both sides by $k+1,$ giving
+$$(k+1)! < (k+1)^{k+1}.$$
+
+We have shown by mathematical induction that for all integers $n>1,$
+$n! < n^n.$
+
+\bye
diff --git a/howard/hw9.tex b/howard/hw9.tex
new file mode 100644
index 0000000..eec9dd4
--- /dev/null
+++ b/howard/hw9.tex
@@ -0,0 +1,144 @@
+\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\nmid{\hskip-3pt\not\hskip2.5pt\mid}
+
+\li Use strong induction to show that the square root of 18 is
+irrational. You must use strong induction to receive credit on this
+problem.
+
+Let $P(n)$ be the proposition that $\sqrt{18} \neq {n\over b}$ for all
+natural numbers $b$ (note: we can assume $b>0$ because $\sqrt{18} > 0$)
+We will $P(n)$ for all nonnegative $n.$
+We will thus conclude that $\sqrt{18}$ is irrational.
+
+We start with the base case $P(0)$ that $\sqrt{18} \neq {0\over b}$ for
+any natural number $b$ (this is clear because $\sqrt{18} \neq 0$).
+
+We now assume for the sake of induction that for all $0\leq j\leq k,$
+for some $k\geq 0,$ $P(j).$
+We will show $P(k+1),$ that $\sqrt{18} \neq {k+1\over b}$ for any
+natural number $b.$
+We assume for the sake of contradiction that $\sqrt{18} = {k+1\over c}$
+where $c\in\bb N.$
+Rearranging,
+$$18c^2 = (k+1)^2.$$
+$(k+1)^2=2(9c^2),$ and $9c^2\in\bb Z$ by closure, so $2\mid (k+1)^2,$ so
+$2\mid k+1$ (if the square of an integer is even, that integer is even).
+
+By definition of even, there exists $l\in\bb Z$ such that $2l = k+1.$
+Also, $4l = (k+1)^2.$
+Substituting, $18c^2 = 4l.$
+With algebra, we obtain $9c^2 = 2l.$
+$2\nmid 9,$ and $2\mid 9c^2,$ so we must have $2\mid c^2.$
+Similarly, this implies $2\mid c,$ so there exists $m\in\bb Z$ such that
+$c = 2m.$
+We now have $\sqrt{18} = {2l\over 2m} = {l\over m},$ and
+$0 < l < k+1,$ contradicting $P(l).$
+We have now shown that $P(0),\ldots,P(k)\impl P(k+1).$
+
+By strong induction, we have shown that $\sqrt{18}$ is not equal to any
+nonnegative rational, so $\sqrt{18}$ is irrational.
+
+\li Use strong induction to show that every integer amount of postage 30
+cents or more can be formed using just 6-cent and 7-cent stamps.
+
+We will first show the base case that all values between 30 and 35 cents
+can be formed from 6- and 7-cent stamps by example: $30 = 6(5)$ and $31
+= 6(4) + 7(1)$ and $32 = 6(3) + 7(2)$ and $33 = 6(2) + 7(3)$ and $34 =
+6(1) + 7(4)$ and $35 = 7(5).$
+
+For the sake of induction we assume that for some $k\geq 30,$ all
+postage amounts from $k$ to $k+5$ can be formed, and we show that
+postage amount $k+6$ can be formed.
+By adding a 6-cent stamp to the formulation for $k$ cents, we achieve a
+formula for $k+6$ cent postage.
+We have shown that being able to form postage of sizes $k$ through
+$k+5$ implies we can form postage of $k+6$ cents.
+
+By strong induction, for all $n\geq 30,$ 6- and 7-cent stamps can form
+$n$ cents of postage.
+
+\li Show that if $a_1,a_2,\ldots,a_n$ are $n$ distinct real numbers,
+exactly $n-1$ multiplications are used to compute the product of these
+$n$ numbers no matter how parentheses are inserted into their product.
+
+We first take the base case that the product of $n=1$ numbers can be
+computed with 0 multiplications (the answer is $a_1$)
+
+Then, for the sake of induction, we assume that for some $k\in\bb N,$
+all multiplications of $1\leq j\leq k$ numbers require exactly $j-1$
+multiplications.
+We will show that multiplying $k+1$ numbers requires $k$ multiplications
+regardless of how the numbers are partitioned (how many parentheses are
+inserted).
+To account for any possible arrangement of upper level parentheses, we
+partition our $k+1$ distinct real numbers into $2\leq r\leq k+1$ sets
+$A_1,A_2,\ldots,A_r.$
+This will require $k-r+1$ multiplications to obtain products for each
+partition, in total:
+$$\sum_{i=1}^r |A_i| = k+1 \Rightarrow \sum_{i=1}^r |A_i| = k-r+1.$$
+We then multiply together the $r$ products which we obtain, requiring
+another $r-1$ multiplications, resulting in $k$ total multiplications,
+regardless of the parenthesis placement we chose.
+
+By strong induction, we have now shown that multiplying $n$ numbers
+always requires $n-1$ multiplications regardless of the position of
+parentheses.
+
+\li Suppose you begin with a pile of $n$ stones and split this pile into
+$n$ piles of one stone each by successively splitting a pile of stones
+into two smaller piles. Each time you split a pile you multiply the
+nmuber of stones in each of the two smaller piles you form, so that if
+the piles have $r$ and $s$ stones in them, you compute $rs.$ Show that
+no matter how you split the stones, the sum of the products compared at
+each step equals $n(n-1)/2.$
+
+We will first show the base case of breaking a pile of 2 stones.
+This pile must be broken into piles of one stone and one stone.
+The product would then be $1 = {n(n-1)\over 2} = {2(2-1)\over 2}.$
+
+We will now assume for the sake of induction that this proposition is
+true for all piles of $j\leq k$ stones where $k\geq 1,$ and we will show
+that this proposition is true for a pile of $k+1$ stones.
+This pile can be broken into a piles of sizes $r$ and $k-r+1,$ where
+$1\leq r\leq k.$
+The sum for each of these piles and the new product is
+$$r(k-r+1)+{r(r-1)\over 2}+{(k-r+1)(k-r)\over 2} =$$$$
+{2rk-2r^2+2r+r^2-r+k^2+r^2-2kr+k-r\over 2} =
+{k^2+k\over2} = {(k+1)k\over 2}.$$
+We have now shown that, assuming all smaller sums for $j$ piles are
+${j(j-1)\over 2},$ $k+1$ stones build the sum ${(k+1)k\over 2}.$
+
+By strong induction, we have shown that for all piles of $n$ stones,
+this process yields a sum ${n(n-1)\over 2}.$
+
+\bye