\documentclass[11pt]{exam}
\usepackage{graphicx}
\usepackage{anysize}
\usepackage{dsfont}
\usepackage{fullpage}
\usepackage{verbatim}
\usepackage{url,amsfonts, amsmath, amssymb, amsthm,color, enumerate, multicol}
\usepackage{placeins}

\printanswers
%\noprintanswers

\begin{document}

\title{ EECS 203: Discrete Mathematics \\
        Individual Homework 4 (Winter 2016)}
\date{Due: May 26, 2016}
\author{Answer Key}

\maketitle

\begin{questions}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\question[2] Section 2.4 Problem 16 (e,f)\\
%%
\begin{solution}
In the iterative approach, we write $a_n$ in terms of $a_{n-1}$, then write $a_{n-1}$ in terms of $a_{n-2}$ (using the recurrence relation with $n - 1$ plugged in for $n$), and so on. When we reach the end of this procedure, we use the given initial value of $a_0$. This will give us an explicit formula for the answer or it will give us a finite series, which we then sum to obtain an explicit formula for the answer.
\begin{enumerate}[a)]
\addtocounter{enumi}{4}
\item \ \\$
\begin{array}{rl}
a_n & =(n+1)a_{n-1}=(n+1)na_{n-2}\\
&=(n+1)n(n-1)a_{n-3}=(n+1)n(n-1)(n-2)a_{n-4}\\
&...\\
&=(n+1)n(n-1)(n-2)(n-3)...(n-(n-2))a_{n-n}\\
&=(n+1)n(n-1)(n-2)(n-3)...2\cdot a_0\\
&=(n+1)!\cdot 2=2(n+1)!
\end{array}
$
\item \ \\$
\begin{array}{rl}
a_n&=2na_{n-1}\\
&=2n(2(n-1)a_{n-2})=2^2(n(n-1))a_{n-2}\\
&=2^2(n(n-1))(2(n-2)a_{n-3})=2^3(n(n-1)(n-2))a_{n-3}\\
&...\\
&=2^nn(n-1)(n-2)(n-3)...(n-(n-1))a_{n-n}\\
&=2^nn(n-1)(n-2)(n-3)...1\cdot a_0\\
&=3\cdot 2^nn!
\end{array}
$
\end{enumerate}
\end{solution}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\question[0] Section 2.5 Problem 28\\
%%
\begin{solution}
We can think of $\mathbb{Z}^+ \times \mathbb{Z}^+$ as the countable union of countable sets, where the ith set in the collection, for $i \in \mathbb{Z}^+$, is $\{(i, n) | n \in \mathbb{Z}^+\}$. The statement now follows from Exercise 27.
\end{solution}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\question[2] Section 3.1 Problem 10\\
%%
\begin{solution}
We assume that if the input $x = 0$, then $n > 0$, since otherwise $x^n$ is not defined. In our procedure, we let $m = |n|$ and compute $x^m$ in the obvious way. Then if $n$ is negative, we replace the answer by its reciprocal.
\begin{verbatim}
procedure power (x : real number, n : integer)
m := |n|
power := 1
for i := 1 to m
    power := power * x
if n < 0 then power := 1/power
return power { power = xn }
\end{verbatim}
\end{solution}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\question[3] Section 3.1 Problem 38\\
%%
\begin{solution}
We start with 6, 2, 3, 1, 5, 4. The first step inserts 2 correctly into the sorted list 6, producing 2, 6, 3, 1, 5, 4. Next 3 is inserted into 2, 6, and the list reads 2, 3, 6, 1, 5, 4. Next 1 is inserted into 2, 3, 6, and the list reads 1, 2, 3, 6, 5, 4. Next 5 is inserted into 1, 2, 3, 6, and the list reads 1, 2, 3, 5, 6, 4. Finally 4 is inserted into 1, 2, 3, 5, 6, and the list reads 1, 2, 3, 4, 5, 6. At each insertion, the element to be inserted is compared with the elements already sorted, starting from the beginning, until its correct spot is found, and then the previously sorted elements beyond that spot are each moved one position toward the back of the list.
\end{solution}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\question[2] Section 3.2 Problem 8\\
%%
\begin{solution}
Note that the following are not quite formal proofs, but that is ok because we are looking for more intuition than proof here.
\begin{enumerate}
\item Since $x^3 \log x$ is not $O(x^3)$ (because the $\log x$ factor grows without bound as $x$ increases), $n = 3$ is too small. On the other hand, certainly $\log x$ grows more slowly than $x$, so $2x^2 + x^3 \log x \leq 2x^4 + x^4 = 3x^4$. Therefore $n = 4$ is the answer, with $C = 3$ and $k = 0$.
\item The $(\log x)^4$ is insignificant compared to the $x^5$ term, so the answer is $n = 5$. Formally we can take $C = 4$ and $k = 1$ as witnesses.
\item For large $x$, this fraction is fairly close to $1$. (This can be seen by dividing numerator and denominator by $x^4$.) Therefore we can take $n = 0$; in other words, this function is $O(x^0) = O(1)$. Note that $n = -1$ will not do, since a number close to $1$ is not less than a constant times $n^{-1}$ for large n. Formally we can write $f(x) \leq 3x^4/x^4 = 3$ for all $x > 1$, so witnesses are $C = 3$ and $k = 1$.
\item This is similar to the previous part, but this time $n = -1$ will do, since for large $x$, $f(x) \approx 1/x$. Formally we can write $f(x) \leq 6x^3/x^4 = 6/x$ for all $x > 1$, so witnesses are $C = 6$ and $k = 1$.
\end{enumerate}
\end{solution}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\question[1] Section 3.2 Problem 22\\
%%
\begin{solution}
The ordering is straightforward when we remember that exponential functions grow faster than polynomial functions, that factorial functions grow faster still, and that logarithmic functions grow very slowly. The order is $(\log n)^3,\sqrt{n} \log n, n^{99} + n^{98} , n^{100} , 1.5^n , 10^n , (n!)^2$.
\end{solution}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\question[1] Section 3.2 Problem 26 (a,c)\\
%%
\begin{solution}
The approach in these problems is to pick out the most rapidly growing term in each sum and discard the rest (including the multiplicative constants).
\begin{enumerate}[a)]
\item This is $O(n^3 \cdot \log n + \log n \cdot n^3)$, which is the same as $O(n^3 \cdot \log n)$.
\addtocounter{enumi}{1}
\item The dominant terms in the two factors are $n^n$ and $n!$, respectively. Therefore this is $O(n^nn!)$.
\end{enumerate}
\end{solution}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\question[4] Section 3.2 Problem 30 (b,e)\\
%%
\begin{solution}
\begin{enumerate}[a)]
\addtocounter{enumi}{1}
\item First, I will show $2x^2+x-7$ is $O(x^2)$.  One witness for this is $C=3$, $k=1$.  Because we know $x\geq 1$, that means $x^2\geq x$, so $$2x^2+x-7\leq 2x^2+x^2-7\leq 2x^2+x^2=3x^2$$
Next, to show $2x^2+x-7$ is $\Omega(x^2)$, one witness is $C=2$, $k=7$.  As long as $x\geq 7$, we know $x-7\geq 0$.  This means $$2x^2+x-7\geq 2x^2+0=2x^2$$
Having shown $2x^2+x-7$ is both $O(x^2)$ and $\Omega(x^2)$, this means it is also $\Theta(x^2)$
\addtocounter{enumi}{2}
\item For brevity, I will use the definition of $\Theta$ in one statement.  Because $\log_{10}x=\frac {\log_2x}{\log_210}$, we can say $$(\log_210)(\log_{10}x)\leq \log_2x\leq (\log_210)(\log_{10}x)$$
This means $C_1=C_2=\log_210$, $k=1$ will work as a witness.
\end{enumerate}
\end{solution}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\question[1] Section 3.3 Problem 18 (a,d)\\
%%
\begin{solution}
We are asked to compute $(2n^2 + 2^n) \cdot 10^{-9}$ for each of these values of n. When appropriate, we change the units from seconds to some larger unit of time.
\begin{enumerate}[a)]
\item $1.224 \times 10^{-6}$ seconds 
\addtocounter{enumi}{2}
\item approximately $1.27 \times 10^{21}$ seconds, which is about $4 \times 10^{13}$ years (nonstop)
\end{enumerate}
\end{solution}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\question[3] How many comparisons does the insertion sort take to  sort n items in the worst case?  What is this Big-Theta of?\\
%%
\begin{solution}
Because $a_j\not<a_j$, we know that the most comparisons we can do each iteration is if $a_j$ is the biggest seen so far, in which case we do $j$ comparisons.  If this happens for every $j$ (i.e. the list was already sorted), it will take $$\sum_{j=2}^nj=\left(\sum_{j=1}^nj\right)-1=\frac{n(n+1)}2-1=\frac{n^2}2+\frac n2-1$$
total comparisons, which is $\Theta(n^2)$
\end{solution}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\question[2] Find $33^4 \mod 32$. Find $(17^5\cdot10) \mod 15$. 
Show your work, no calculators (both are trivial)\\
%%
\begin{solution}
$33^4\equiv 1^4\equiv1 \mod 32$

$17^5\cdot10\equiv 2^5\cdot10\equiv32\cdot 10\equiv 2\cdot 10\equiv 20\equiv 5\mod 15$
\end{solution}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\question[1] Section 4.2 Problem 2 (a), 4 (a), 6 (a,d)\\
%%
\begin{solution}\ \\
2. To convert from decimal to binary, we successively divide by 2. We write down the remainders so obtained from right to left; that is the binary representation of the given number.

a) Since 321/2 is 160 with a remainder of 1, the rightmost digit is 1. Then since 160/2 is 80 with a remainder of 0, the second digit from the right is 0. We continue in this manner, obtaining successive quotients of 40, 20, 10, 5, 2, 1, and 0, and remainders of 0, 0, 0, 0, 1, 0, and 1. Putting all these remainders in order from right to left we obtain $(1\ 0100\ 0001)_2$ as the binary representation. We could, as a check, expand this binary numeral: $2^0 + 2^6 + 2^8 = 1 + 64 + 256 = 321$.

4. a) $1 + 2 + 8 + 16 = 27$

6. We follow the procedure of Example 7.

a) $(1111\ 0111)_2 = (011\ 110\ 111)_2$ = $(367)_8$

d) $(101\ 0101\ 0101\ 0101)_2 = (101\ 010\ 101\ 010\ 101)_2 = (52525)_8$
\end{solution}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\question[2] Section 4.2 Problem 26\\
%%
\begin{solution}
In effect, this algorithm computes $11 \mod 645$, $11^2 \mod 645$, $11^4 \mod 645$, $118 \mod 645$, $11^{16} \mod 645$, ... , and then multiplies (modulo 645) the required values. Since $644 = (1010000100)_2$ , we need to multiply together $11^4 \mod 645$, $11^{128} \mod 645$, and $11^{512} \mod 645$, reducing modulo 645 at each step. We compute by repeatedly squaring: $11^2 \mod 645 = 121$, $11^4 \mod 645 = 121^2 \mod 645 = 14641 \mod 645 = 451$, $11^8 \mod 645 = 451^2 \mod 645 = 203401 \mod 645 = 226$, $11^{16} \mod 645 = 226^2 \mod 645 = 51076 \mod 645 = 121$. At this point we notice that 121 appeared earlier in our calculation, so we have $11^{32} \mod 645 = 121^2 \mod 645 = 451$, $11^{64} \mod 645 = 451^2 \mod 645 = 226$, $11^{128} \mod 645 = 226^2 \mod 645 = 121$, $11^{256} \mod 645 = 451$, and $11^{512} \mod 645 = 226$. Thus our final answer will be the product of $451$, $121$, and $226$, reduced modulo $645$. We compute these one at a time: $451 \cdot 121 \mod 645 = 54571 mod 645 = 391$, and $391 \cdot 226 \mod 645 = 88366 \mod 645 = 1$. So $11^{644} \mod 645 = 1$. A computer algebra system will verify this; use the command “11  \&\^\  644 mod 645;” in Maple, for example. The ampersand here tells Maple to use modular exponentiation, rather than first computing the integer 11644 , which has over 600 digits, although it could certainly handle this if asked. The point is that modular exponentiation is much faster and avoids having to deal with such large numbers.
\end{solution}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\question[1] Section 4.2 Problem 40 (a,c)\\
%%
\begin{solution}
Following the definition, we find the two’s complement expansion of a positive number simply by representing it in binary, using six bits; and we find the two’s complement expansion of a negative number $-x$ by representing $2^5 - x$ in binary using five bits and preceding it with a $1$.

\begin{enumerate}[a)]
\item Since 22 is positive, and its binary expansion is 10110, the answer is 010110.
\addtocounter{enumi}{1}
\item Since −7 is negative, we first find the 5-bit binary expansion of $2^5 - 7 = 25$, namely $11001$, and precede it by a 1, obtaining 111001.
\end{enumerate}
\end{solution}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\question[1] Section 4.3 Problem 30\\
%%
\begin{solution}
By Exercise 31 we know that the product of the greatest common divisor and the least common multiple of two numbers is the product of the two numbers. Therefore the answer is $(2^7\cdot3^8\cdot5^2\cdot7^{11})/(2^3\cdot3^4\cdot5) = 2^4\cdot3^4\cdot5\cdot7^{11}$ .
\end{solution}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\question[1] Section 4.3 Problem 32 (d)\\
%%
\begin{solution}
To apply the Euclidean algorithm, we divide the larger number by the smaller, replace the larger by the smaller and the smaller by the remainder of this division, and repeat this process until the remainder is 0. At that point, the smaller number is the greatest common divisor.
\begin{enumerate}[a)]
\addtocounter{enumi}{3}
\item $\gcd(1529, 14039) = \gcd(1529, 278) = \gcd(278, 139) = \gcd(139, 0) = 139$
\end{enumerate}
\end{solution}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\question[3] Section 4.3 Problem 42\\
%%
\begin{solution}\ \\$
\begin{array}{rl}
356&=1\cdot252+104\\
252&=2\cdot104+44\\
104&=2\cdot44+16\\
44&=2\cdot16+12\\
16&=1\cdot12+4\\
12&=3\cdot4+0\\
\end{array}$\\
This tells us that $\gcd(252,356)=4$.  Solving each of the above equations for the remainders, we get:\\
$\begin{array}{rl}
4&=16-1\cdot 12\\
12&=44-2\cdot 16\\
16&=104-2\cdot 44\\
44&=252-2\cdot104\\
104&=356-1\cdot 252\\
\end{array}$\\
We start with the first equation and repeatedly substitute in the next one:\\
$\begin{array}{rlll}
4&=16-1\cdot 12\\
&=16-1\cdot(44-2\cdot 16)&=16-1\cdot 44+2\cdot 16&=3\cdot 16-1\cdot 44\\
&=3\cdot(104-2\cdot 44)-1\cdot 44&=3\cdot 104-6\cdot 44-1\cdot 44&=3\cdot 104-7\cdot 44\\
&=3\cdot 104-7\cdot(252-2\cdot 104)&=3\cdot 104-7\cdot 252+14\cdot 104&=17\cdot 104-7\cdot 252\\
&=17\cdot (356-1\cdot 252)-7\cdot 252&=17\cdot 356-17\cdot 252-7\cdot 252&=17\cdot 356-24\cdot 252\\
\end{array}$\\
We can therefore say $4=17\cdot 356+(-24)\cdot 252$
\end{solution}


\end{questions}

\end{document}