\documentclass[12pt]{article}
\usepackage{latex-macros/course}% !! use the macros

\newcommand{\rem}{\operatorname{\,rem\,}}
\newcommand{\lngth}[1]{\operatorname{length}\paren{#1}}

\instatements{
\renewcommand{\exampreamble}{   % !! renew \exampreamble 
  \textbf{Circle the name of your Tutorial Instructor}:
  \begin{center}
  \renewcommand{\arraystretch}{1.5}
  \begin{tabular}{cccc}
  David    & Hanson   & Jelani & Sayan
  \end{tabular}
  \end{center}
  \begin{itemize}
  \item 
  This quiz is \textbf{closed book} except for a personal one-page crib
  sheet.  No calculators either.
  \item 
  There are 6 problems totaling 100 points.  
  Problems are labeled with their point values.
  You may assume any of the results presented in class or in the lecture
  notes.  Total time is 80 minutes.
  \item 
  Write your solutions in the space provided.  If you need more
  space, write on the back of the sheet containing the problem.
  Please keep your entire answer to a problem on that problem's page.
  Incorrect short answers can receive partial credit only if work is
  clearly shown.
\iffalse
  \item  
  \textbf{Be neat and write legibly}.  You will be graded not only on
  the correctness of your answer, but also on the clarity with which
  you express it.
\fi
  \item 
  GOOD LUCK!
  \end{itemize}}
}

\begin{document}
\quiz{2}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%\instatements{\newpage}

\begin{examproblem}{10} True/False.  Circle the appropriate answer.
\bparts
\ppart[2] A state machine with a strictly decreasing derived variable must
terminate.
\begin{center}
\textbf{\hspace{1in} True \hspace{1in} False} 
\end{center}
\solution[\vspace{0.5in}]{F}
\ppart[2] In a set of stable marriages with more than one couple, it is
possible for everyone to be married to the person at the bottom of their
preference list.
\begin{center}
\textbf{\hspace{1in} True \hspace{1in} False} 
\end{center}
\solution[\vspace{0.5in}]{F: every couple would be a rogue couple.}
\ppart[2] An infinite geometric sum whose ratio between successive terms
is $r$ converges if $\abs{r} \leq 1$.
\begin{center}
\textbf{\hspace{1in} True \hspace{1in} False} 
\end{center}

\solution[\vspace{0.5in}]{F when $r = 1$.}
\ppart[2]  Four books can be stacked at the edge of a table so that
the top book lies completely over the edge of the table. 
\begin{center}
\textbf{\hspace{1in} True \hspace{1in} False} 
\end{center}
\solution[\vspace{0.5in}]{T, as observed in the Notes.}
\ppart[2] The security of RSA relies on the assumption that the ability to
decipher RSA-encrypted messages efficiently would imply the ability to
factor key-sized numbers efficiently.
\begin{center}
\textbf{\hspace{1in} True \hspace{1in} False} 
\end{center}
\solution{The correct answer is F. The security of RSA is shakier than the presumed difficultly
of factoring, as noted in a pset. Very few students got this right, and since we did not adequately 
define what security formally means, we  awarded 2 points to everyone.}
\eparts
\end{examproblem}


\instatements{\newpage}
\begin{examproblem}{20}
\bparts 
\ppart[10] 
Using the Pulverizer, find an $x$ in the range $[0\dots 99]$ such 
that $x$ is an inverse of 19 modulo 100.
\solution[\vspace{3.5in}]{There are two valid approaches.
\textbf{Solution 1:} Use the Pulverizer to find integers $s,t$ such that
$s19+t100 =1$.  Then $s \rem 100$ will be $19^{-1}$.
In this case the Pulverizer yields $-21\cdot 19 + 4 \cdot 100 =1$, so
$19^{-1} \equiv -21 \equiv 79 \pmod {100}$.
\textbf{Solution 2:} Find $k =\phi(100)$, so by Euler's Theorem, $19^{-1}
\equiv 19^{k-1} \pmod{100}$.  Then $19^{k-1} \rem 100$ will be $19^{-1}$.
This can be computed by at most $\floor{\log 100} = 6$ squarings modulo
100.
}
\ppart[5] What is the value of $\phi(360)$, where $\phi$ is Euler's
function? \hfill\brule{4em}
\solution[\vspace{1.5in}]{Note that $360=2^3\cdot3^2\cdot5$.  It follows that
$\phi(360)=4\cdot6\cdot4=96$.}

\ppart[5] What is the value of $7^{98} \rem 360$? \hfill\brule{4em}
\solution{Since 7 and 360 are relatively prime, we have by Euler's Theorem
that $7^{96} \equiv 1 \pmod {360}$, and so
\[
7^{98} = 7^{96}\cdot 7^2 \equiv 1 \cdot 49 \equiv 49 \pmod {360}.
\]
}
\eparts
\end{examproblem}

\instatements{\newpage}
\begin{examproblem}{15} Consider the following functions:
\[\begin{array}{llll}
f_1(n) = \log (n!) &\quad f_2(n) = 10^{100}
   &\quad f_3(n) = \sum_{i=1}^n (1/i) 
   &\quad  f_4(n) =  \log(4^n)\\
f_5(n) = \log(n^n) &\quad f_6(n) = 2+\sin n  &\quad f_7(n) = \log (6^n)
\end{array}\]
\iffalse
\begin{alignat*}{3}
f_1(n) = & \frac{n}{\ln n} &\qquad f_4(n) = & \log n! &\qquad 
  f_7(n) = & 10^{100} \\
f_2(n) = & (\ln n)^2 &\qquad f_5(n) = & \sum_{i=1}^n \frac{1}{i} &\qquad 
  f_8(n) = & \log(4^n) \\
f_3(n) = & \log(n^n) &\qquad f_6(n) = & \sin n &\qquad 
  f_9(n) = & \log(2^n)
\end{alignat*}
\fi
\bparts
\ppart[10] List the digits $1,\dots,7$ in an order such that if digit $i$
comes before $j$ in your list, then $f_i=O(f_j)$.
\begin{center}
\brule{2in}
\end{center}
\solution[\vspace{3in}]{2, 6, 3, 4, 7, 1, 5. }
\ppart[5] List a sequence of sets of the digits so that $i$ and $j$ are in
the same set iff $f_i = \Theta(f_j)$.  Write your list in a form such as
``$\{543\}, \{76\}, \{21\}$''.
\begin{center}
\brule{3in}
\end{center}
\solution{$\{2,6\} \{3\} \{4,7\} \{1,5\}.$}
\eparts
\end{examproblem}

\instatements{\newpage}
\begin{examproblem}{20} Write simple formulas for the following quantities.  You
do not have to calculate numerical values for the formulas.
\bparts
\ppart[6] The number of rearrangements of the word $BAZOOKA$ in which the
two O's do not appear next to each other.
\solution[\vspace{1.5in}]{
Total number of arrangements is:
\begin{equation}\label{tot}
\binom{7}{2,2,1,1,1} = \frac{7!}{2!\,2!} = 1260.
\end{equation} 
The number of arrangements in which the two O's \emph{do} appear next to
each other is the number of rearrangements of $BAZOKA$ since we can treat
the double-O as though it was a single O:
\[
\binom{6}{2,1,1,1,1} = \frac{6!}{2!} = 360.
\]
Therefore, the number of arrangements in 
which the O's do {\em not} appear together is: 
\[
\binom{7}{2,2,1,1,1} - \binom{6}{2,1,1,1,1} = 1260 - 360  =  900.
\]
}
\ppart[6] The number of rearrangements of the word $BAZOOKA$ in which the
two O's do not appear next to each other \emph{and} that do not start
with $B$.
\solution[\vspace{1.5in}]{Total number of arrangements that \emph{do}
start with B is the number of rearrangements of $AZOOKA$:
\[
\binom{6}{2, 2, 1,1} = \frac{6!}{2!\,2!} = 180.
\] 
Number of arrangements starting with B {\em and} with two O's next to each
other is the number of arrangements of $AZOKA$:
 \[ 
\binom{5}{2, 1, 1,1} = \frac{5!}{2!} = 60.
\] 
By inclusion-exclusion it follows that the number of arrangements in which
the two O's appear together \emph{or} that start with B is the number that
have two O's together plus the number that start with B, minus the number
that do both:
\begin{equation}\label{OOorB}
360 + 180 - 60 = 480.
\end{equation}
So the number that neither have two O's next to each other nor start with
B is the total~\eqref{tot} minus those that do one or the other
~\eqref{OOorB}, namely
\[
1260 - 480 = 780.
\]} 

\ppart[2] The number of \textit{nonnegative integer} solutions to the
equality:
\[
x_1+x_2+ \ldots +x_{10} = 100.
\]
\solution[\vspace{0.7in}]{There is a bijection from the set of
nonnegative solutions to the above equation to the set of 109 bit binary
strings with exactly 9 1's.  The number of such binary strings is:
\[
\binom{100+9}{9}.
\]
}
\ppart[6] The number of \textit{positive integer} solutions
to the inequality:
\[
x_1+x_2+ \ldots +x_{10} \leq 100.
\]
\solution[\vspace{1in}]{There is an immediate bijection between the
number of \emph{positive} solutions to the above inequality:
\begin{equation}\label{i10}
x_1+x_2+ \ldots +x_{10} \leq 100,
\end{equation}
and the number of solutions to the equality
\begin{equation}\label{e10}
x_1+x_2+ \ldots +x_{10} + x_{11} = 100,
\end{equation}
in which the first ten variables are positive.
Then, the mapping which subtracts 1 from the positive values of
$x_1,x_2,\dots, x_{10}$ is a bijection between these solutions
of~\eqref{e10} and the nonnegative solutions of
\[
x_1+x_2+ \ldots +x_{10} + x_{11} = 100 - 10 = 90,
\]
which we know the same as the number of $90+10$ bit strings with 10 one's,
namely:
\[
\binom{100}{10}.
\]
}
\eparts
\end{examproblem}

\instatements{\newpage}
%\begin{examproblem}{15} Show that 
%\[
%n^4 = O(\sum_{i=1}^n i^3)
%\]

%\solution{Integral method, or bound the sum by
%$\sum_{i=n/2}^n (n/2)^3=n^4/16$ below.
%\iffalse  and by $\sum_{i=1}^n n^3=n^4$ above\fi
%}

\begin{examproblem}{10}
To prove that $n^4 = O(\sum_{i=1}^n i^3)$ we can use the integral method to
bound the sum.  In particular, we should obtain a(n)
\begin{center}
        upper \qquad  lower  \qquad\qquad              (CIRCLE THE RIGHT CHOICE)
\end{center}
bound on the sum that is equal to the value of $\int_a^b (x+c)^d dx$ where
\begin{center}
       $a$ is \brule{0.5in}, \hfill $b$ is \brule{0.5in}, \hfill  $c$ is
       \brule{0.5in}, and \hfill $d$ is \brule{0.5in}.
\end{center}
\solution{The sum must be greater than $\epsilon n^4$ for some positive
$\epsilon$ in order for $n^4$ to be O(the sum).  That is, we need such a
\textbf{lower} bound on the sum.  To do this, we choose the constants so
that integral is $\leq$ the sum, and is also $>\epsilon n^4$.
Choosing $d=3$, and $a=0, b=n, c=0$, for example, will do the job.  It
would also be OK to increase this value for $a$ by a constant (say $a=1$),
and decrease $c$ by the same constant (say $c=-1$), and decrease the value
of $b$ by a constant (say $b= n-2$).}
\end{examproblem}


\instatements{\newpage}
\begin{examproblem}{25}
We will describe a process that operates on sequences of numbers.
The process will start with a sequence that is some \emph{permutation} of
the length $4n$ sequence
\[
(1,2,\dots,n,1,2,\dots,n,1,2,\dots, 2n).
\]
\bparts
\ppart[7]\label{start} Write a simple formula for the number of possible starting
sequences.
\solution[\vspace{1.0in}]{
Using the Bookkeeper rule: $4n$ digits can be arranged in $4n!$ ways; 
each digit from $1$ to $n$ appears 3 times.
Therefore, we have to divide $4n!$ by $3!\ldots3!$, $n$  times.
The answer is:
\[
\frac{(4n)!}{(3!)^n}
\]
}
\eparts
If $(s_1,\dots,s_k)$ is a sequence of numbers, then the $i$ and $j$th
elements of the sequence are \emph{out of order} if the number on the left
is strictly larger the number on the right, that is, if $i<j$ and $s_i >
s_j$.  Otherwise, the $i$th and $j$th elements are \emph{in order}.
Define $p(S) \eqdef$ the number of ``out-of-order'' pairs of 
elements in a sequence, $S$.
For example, if $S$ is the sequence
\[
(3,4,2,1,7,3),
\]
then the 1st and 3rd elements of $S$, (namely, 3 and 2), are out of order, but
the 3rd and 6th elements (2 and 3) are in order.  The 1st and 6th elements
of $S$ are also in order, since they are both 3.  In this case, $p(S)=7$.
The \emph{reversal} of $(s_1,\dots,s_k)$ is $(s_k,\dots,s_1)$.  So the
reversal of the sequence $S$ is 
\[
(3,7,1,2,4,3).
\]
From the starting sequence, we carry out the following process:
(*) Pick two consecutive elements in the current sequence, say the $i$th
and $(i+1)$st.
\begin{enumerate}
\item[I.] If the elements are not in order, then \textbf{switch them} in
the sequence and repeat step (*).
\item[II.] If the elements are in order, \textbf{remove both}, resulting
in a sequence that is shorter by two.  If the length of the resulting
sequence is zero or one, the process is over.  Otherwise, \textbf{reverse
the sequence} and repeat step (*).
\end{enumerate}
This process can be modelled as a state machine where the states are the
sequences that appear at step (*).  We then consider the derived variables
on the following page:
\instatements{\newpage}
\begin{enumerate}
\item[i.] $p(S)$ \hfill\brule{0.4in}
\solution{None of the Above.   \textbf{(2 pts)}
Reversing a sequence maps an out-of-order pairs of elements into an in
order pair of elements with different values.  Pairs of elements with the
same values stay in order.  So the number of out of order pairs can
increase \emph{or} decrease depending on whether there were more
out-of-order than strictly in order pairs.}
\item[ii.] $\lngth{S} \rem 2$ \hfill\brule{0.4in}
\solution{Constant.   \textbf{(2 pts)}
$\lngth{S}$ changes by 0 or 2 at each transition, it parity is unchanged.
}
\item[iii.] $\lngth{S} + p(S)$ \hfill\brule{0.4in}
\solution{None of the Above.   \textbf{(3 pts)}
While $\lngth{S}$ decreases by 2 or is unchanged, $p(S)$ may go up or down
by more than 2.}
\item[iv.] $\max \paren{p(S), 8n^2}$ \hfill \brule{0.4in}
\solution{Constant.   \textbf{(3 pts)}
Since there are only $\binom{4n}{2} < 8n^2$ pairs of distinct positions in
a length $4n$ sequence, at most this many can be out of order (even fewer
because there will be $3$ pairs of elements with the same value for each
of the values $1,\dots,n$) and $p(n) \leq $ the total number of such
pairs.}
\item[v.] $4n^2 \cdot \lngth{S}+ p(S)$ \hfill\brule{0.4in}
\solution{Strictly Decreasing.   \textbf{(4 pts)}
In the first transition, $p(S)$ decreases and $\lngth{S}$ stays the same.
The quantity decreases.  In the second transition, the $4n^2\lngth{S}$
decreases by $8n^2$.  But $p(S)$ can't change by more than its maximum
value, which by the previous part is $\leq \binom{4n}{2} < 8n^2$.  So the
quantity decreases in this case too.}
\end{enumerate}
\bparts
\ppart[14] Indicate next to each of the derived variables above
which one of these properties it has:
\begin{center}
\begin{tabular}{|ll|} \hline
constant              & C  \\  
strictly increasing   & SI \\
strictly decreasing   & SD \\
weakly increasing but not constant & WI \\
weakly decreasing but not constant & WD \\
none of the above     & N  \\\hline
\end{tabular}
\end{center}
\ppart[2] Which of the variable behaviors in i.--v.\ above immediately
implies that the process will definitely terminate? \hfill\brule{0.5in}
\solution{v.  Fact~v.\ implies termination by the Well Ordering
Principle.}
\ppart[2] Which of the variable behaviors in i.--v.\ above immediately
implies that, starting from any of the possible starting states from
part~\eqref{start}, the process will not terminate with a length 1
sequence?  \hfill \brule{0.5in}
\solution{ii.  Since every possible start state has length $4n$, Fact~ii.\
implies that every reachable state must be of even length, and so cannot
be length 1.}
\eparts
\end{examproblem}

\end{document}
