\documentclass[12pt]{article}
\usepackage{amsmath}

\input{macros-course}

\def\brule#1{\enskip\vrule width#1 height -1.1pt depth 1.5pt\relax}

\newcommand{\ignore}[1]{}
\newcommand{\solution}[1]{}
%%  \newcommand{\solution}[1]{\smallskip \textbf{Solution:} #1}

\newcommand{\pts}[1]{\relax[#1 pts]\enskip\ignorespaces}

\makeatletter
%%  \renewcommand\theenumi{\@alph\c@enumi}
%%  \renewcommand\theenumii{\@roman\c@enumii}
%%  
%%  \renewcommand\labelenumi{\theenumi)}
%%  \renewcommand\labelenumii{\theenumii)}

\def\ps@myheadings{%
    \let\@oddfoot\@empty\let\@evenfoot\@empty
    \def\@evenhead{\thepage\hfil\slshape\leftmark}%
    \def\@oddhead{\rlap{\slshape\rightmark}\hfil\thepage\hfil \llap{Name:\brule{2in}}}%
    \let\@mkboth\@gobbletwo
    \let\sectionmark\@gobble
    \let\subsectionmark\@gobble
    }

\makeatother

\newcommand{\bij}{\mathop{\mbox{\rm bij}}}

\begin{document}

\handout{}{Conflict Quiz 2}{April 15, 1999}

\textbf{Your Name}:\ \mbox{}\hrulefill\mbox{}\par

\textbf{Circle the name of your TA}:\\
\begin{center}
\begin{tabular}{lll}
Matt Blum & Stas Jarecki\&Eric Lehman & Amit Khetan\\
Mike Leonida & Zulfi Ramzan & Jared Smith-Mickelson
\end{tabular}
\end{center}

\medskip

\begin{closeitemize}
\item This quiz is \textbf{closed} book, except for a one-page sheet of
notes you have prepared.  No calculators either.

\item There are six (6) problems totaling 100 points.  Problem parts are
labelled with their point values.

\item Put your name on the top of {\bf every} page --- \emph{these pages
will be separated for grading}.

\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.

\iffalse
\item Show your work, as partial credit will be given.  You will be
graded not only on the correctness of your answer, but also on the
clarity with which you express it.  {\bf Be neat}.
\fi

\item GOOD LUCK!
\end{closeitemize}

\bigskip

\iffalse
\noindent Write the hour at when your Friday recitation begins \brule{3em}

\medskip
\fi

\hrule
\smallskip
\centerline{\textbf{DO NOT WRITE BELOW THIS LINE}}
\smallskip
\hrule

\medskip

\begin{center}
\renewcommand{\arraystretch}{.3}
\begin{tabular}{|c|c|c|c|}
\hline
& &\hspace*{1in}&\\
Problem & Points & Grade & Grader\\
& & & \\ \hline \hline
& & & \\
1 &  16 & & \\ & & & \\\hline & & &\\
2 &  20 & & \\ & & & \\\hline & & &\\
3 &  18 & & \\ & & & \\\hline & & &\\
4 &  15 & & \\ & & & \\\hline & & &\\
5 &  13 & & \\ & & & \\\hline & & &\\
6 &  18 & & \\ & & &\\
\hline
\hline
& & &\\
Total & 100 & & \\
& & &\\
\hline
\end{tabular}
\end{center}

\newpage

\begin{problems}

\problem\pts{16} \emph{Divide and Conquer.}

The easily-applied version of the Master Theorem for Divide and Conquer
recurrences given in tutorial is stated below.  In the indicated space
next to each of the following recurrences, write an ``X'' if this Master
Theorem does not directly apply to it.  If it does directly apply, then
write the $\Theta()$ bound given by the Theorem for this recurrence.

\[\begin{array}{rclrclr}
T(n) & = & 3T(\ceil{n/2}) + n^{\log_2 3} & \brule{2.0in}\\
& \\
& \\
T(n) & = & T(n) - n^2 & \brule{2.0in}\\
&\\
& \\
T(n) & = & 3T(\ceil{n/2}) + n\log_2 n & \brule{2.0in}\\
& \\
& \\
T(n) & = & 3T(n-1) + 2T(n-2) & \brule{2.0in}\\
& \\
& \\
T(n) & = & 3T(\ceil{n/2}) + n^{\log_2 3}\log_2 n & \brule{2.0in}\\
& \\
& \\
T(n) & = & \frac{1}{2}T(\ceil{n/2}) + 1/\sqrt{n} & \brule{2.0in}\\
& \\
& \\
T(n) & = & 2T(\ceil{n/2}) + n^{\log_2 3} & \brule{2.0in}\\
& \\
& \\
T(n) & = & T(\ceil{n/5}) + T(\ceil{3n/4}) + 11 & \brule{2.0in}
\end{array}\]

\begin{theorem*}[Divide-And-Conquer Master Theorem]
\label{master}
Suppose
\[
T(n) = aT(\ceil{n/b}) + f(n)
\]
where $T,f:\naturals\to \reals, a > 0,$ and $b >1$.
Let $\beta ::= \log_b a$.  Then
\[
T(n) = \left\{ \begin{array}{ll}
\Theta(n^\beta) & \mbox{ if } f(n) = O(n^\alpha)\mbox{ for some } \alpha < \beta,\\
\Theta(n^\beta \log n) & \mbox{ if } f(n) = \Theta(n^\beta),\\
\Theta(n^\alpha) & \mbox{ if } f(n) = \Theta(n^\alpha) \mbox{ for some } \alpha > \beta.\\
\end{array} \right.
\]
\end{theorem*}


\newpage
\problem\pts{20}\emph{Linear Recurrences.}

Solve the linear recurrence
\[
T(n) = 3T(n-1) - 4T(n-3) + 6
\]
subject to the initial conditions $T(0) = 11, T(1) = 6, T(2) = 28$.

\solution{
(a)  Solve the homogeneous equation.

The characteristic equation of the homogeneous part is $x^3 -3x^2+4=0$
which has -1 as a root and 2 as a double root.  So
\[
T(n) = a 2^n + b n 2^n + c (-1)^n,
\]
for any constants $a,b,c$.

(b) Obtain the particular solution.  $T(n) \equiv 3.$

(c) Now, solve the recurrence by adding the homogeneous solution to the
   particular solution and solving for the base cases.
\[
T(n) = a 2^n + b n 2^n + c (-1)^n + 3
\]
where $a = 3, b = 1, c = 5$.}


\vfill

\newpage

\problem\pts{18} \emph{Bijections.}
\bparts

\ppart\pts{4} Give an example of an infinite set, $A$, such that there is
no injection from $A$ into the set, $\reals$, of real numbers.

\solution{$P(\reals)$}

\vspace{1.5in}
\ppart\pts{4} Give an example of an infinite set, $A$, such that there is
no injection from $\reals$ into $A$.

\solution{$\naturals$}

\vspace{1.5in}

\ppart\pts{10} Prove that the set of all finite sequences of integers is
countable.

\solution{We know $\integers$ is countable, and the product of two, and
hence any finite number of, countable sets is countable.  So the set
$\integers^k$ of length $k$ intger sequences is countable, and since a
countable union of countable sets is countable, so is the set $\cup_k
\integers^k$ of all finite sequences of integers.}

\eparts

\vfill

\newpage
\problem\pts{15} \emph{Inclusion-exclusion.}

There are 130 students in 6.042.  Some students are blessed with one or
more of the qualities of being healthy, wealthy, and/or lucky.  A few
students are cursed by the lack of all these qualities.  Moreover,
\begin{enumerate}

\item every student that is both healthy and wealthy is also lucky,

\item half of the lucky students are healthy,

\item half of the lucky students are wealthy,

\item seventy (70) students are healthy, and

\item thirty (30) students are wealthy.

\end{enumerate}
Exactly how many cursed students are there in 6.042?

\solution{
By inclusion-exclusion, we have:
\[
\card{\mbox{blessed students}} = H + W + L - HW - HL - WL + HWL
\]
where the letter strings on the right side represent cardinalities of
intersections, e.g., $HW = \card{\mbox{students who are healthy and
wealthy}}$.

Fact 1 implies that $HW = HWL$, and thus these two
terms cancel, leaving:

\[
\card{\mbox{blessed students}} = H + W + L - HL - WL
\]

Facts 2 and 3 imply that $HL = L / 2$ and $WL = L / 2$.  Substitution
gives:

\[
\card{\mbox{blessed students}} = H + W + L - (L / 2) - (L / 2)
      = H + W = 70 + 30 = 100.
\]
Fact 4 now gives the final answer:

\[
\card{\mbox{cursed students}}= 130 - \card{\mbox{blessed
      students}} = 30.
\]}

\newpage
\problem\pts{13} \emph{Permutations and Combinations.}
\[
k \binom{n}{k} = n \binom{n-1}{k-1}
\]

\bparts
\ppart\pts{4} Prove this equation algebraically.

\vfill

\newpage

\ppart\pts{9} Now give a combinatorial argument proving this equation.
That is, describe two different procedures for counting the same things,
where the lefthand side of the equation clearly describes the number of
outcomes of the first procedure and the righthand side the number of
outcomes of the second procedure.

\solution{Two ways to choose a committee of $k$ out of $n$ and a committee
chair:
\begin{enumerate}
\item The LHS corresponds to choosing the committee of $k$ and then
choosing a chair among the $k$.
\item The RHS corresponds to choosing one of the $n$ to be the chair, and
then choosing the remaining $k-1$
committee members from the remaining $n-1$ people.
\end{enumerate}
}

\eparts
\vfill

\newpage
\problem\pts{18} \emph{Stars and Bars.}  The \emph{king positioning} in an
arrangement of a deck of 52 playing cards is the sequence of numerical
positions in the deck, from one to 52, of the four successive kings.  For
example, the king positioning $(1,2,3,4)$ means all the kings come at the
beginning of the deck.  The king positioning $(1,18,35,52)$ describes the
situation in which the kings are spaced uniformly---with exactly 16 cards
between successive kings.

Your answer to each of the following questions may be an arithmetic
expression involving factorials and/or multinomial coefficients.

\bparts
\ppart\pts{4} How many king positionings are there?

\solution{$\binom{52}{4}$.}

\vspace{1.5in}

\ppart\pts{8} How many king positionings are there in which \emph{no two
kings are adjacent}?

\solution{Think of kings as bars and the remaining 48 cards as stars.
Place one star between each two adjacent kings (bars).  This requires
three stars and leaves 45 stars that can be placed anywhere; there are
$\binom{45+4}{4}$ ways to do this.}

\vspace{1.5in}

\ppart\pts{6} Of the $52!$ possible arrangements of the deck, how many
have no two kings adjacent?

\solution{Now in each of the previous patterns of stars and bars, the
kings can be permuted in $4!$ ways and the remaining cards can be permuted
in $48!$ ways, so the total number of desired arrangements is
\[\binom{45+4}{4} 48!\, 4! = 49!\, 48!/45! = 48!\, P(49,4).\]

\iffalse
The form of the RHS suggests that there is another way to do this count,
but I haven't had time to figure what it is.
\fi
}

\eparts

\vfill
\end{problems}

\end{document}
