%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% This is Quiz 2 from Spring 2000 (edited)
%%

\documentclass[11pt]{article}

\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{psfig}
\input{macros-course}


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

\newcommand{\bij}{\mathbin{\mbox{\rm bij}}}
\newcommand{\inj}{\mathbin{\mbox{\rm inj}}}
\newcommand{\sur}{\mathbin{\mbox{\rm sur}}}
\newcommand{\ran}[1]{\text{range}(#1)}
\newcommand{\Union}{\bigcup}

\newcommand{\eqdef}{\mathbin{\mbox{::=}}}

\newcommand{\ROT}{\mbox{ROT}}
\newcommand{\FBT}{\mbox{FBT}}
\newcommand{\brep}{\mbox{rot-to-fbt}}
\newcommand{\unrep}{\mbox{fbt-to-rot}}
\newcommand{\nil}{\mbox{\texttt{()}}}
\newcommand{\sz}{\mbox{size}}
\newcommand{\cons}{\mbox{cons}}
\newcommand{\sbtr}{\mbox{subtrees}}
\newcommand{\kcomp}[1]{\bar{#1}}

\newcommand{\kth}{\ensuremath{^{\textrm{\tiny th}}}}

\newcommand{\fins}{\mathcal{F}}

\newcommand{\kpfend}{}

\newcommand{\kskip}[1]{}

\newcommand{\pts}[1]{\relax[#1 points]\enskip\ignorespaces}
\newcommand{\onept}{\relax[1 point]\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

\askaboutsolutions

\begin{document}

\ifshowsolutions
\pquizsol{2}{November 10, 2000}
\else
\pquiz{2}{November 7, 2000}
\fi

\begin{problems}

\problem\pts{10}

Consider $n>1$ people that attend a party.  Prove that there must be
two people who greet the same number of distinct people; assuming no
one greets his/her self.

\solution{\textbf{Solution: }
A straightforward application of the pigeonhole principle.
Since no person can greet himself, the number of people he can greet
must be an integer from $0$ to $n-1$.  If no two people greet the same
number of people, then every one of these $n$ numbers from $0$ to
$n-1$ must equal the number of greetings some person made.  But that
would mean that some person greets $0$ people while some other person
greets $n-1$ people, i.e., all the other people.  This is a
contradiction.  }

\problem\pts{20}\textbf{Counting}

For the problems below, you may leave products and binomial
coefficients in your final answer.  Moreover, you should assume that a
deck of cards consists of 52 cards; that is, 4 suits of 13 cards each
($2,3,4, \ldots, 9, 10, J, Q, K, A$).

\bparts
\ppart\pts{5} In poker, a \emph{flush} is a set of five cards, all of the
same suit.  How many distinct flushes are there?
 
\solution{\textbf{Solution: }
$4\cdot\binom{13}{5}$: 4 for the suit, $\binom{13}{5}$ for the
cards chosen within that suit.}

\ppart\pts{5} %
In poker, a \emph{straight} is a set of five cards that, when the
suits are ignored, form a five-in-a-row sequence, for example
$5,6,7,8,9$ or $8,9,10,J,Q$.  An ace can start a straight
($A,2,3,4,5$) or end it ($10,J,Q,K,A$) but cannot wrap around ({\bf
  no} $Q,K,A,2,3$).  How many distinct straights are there?

\solution{\textbf{Solution: }
$4^5\cdot 10$: 4 suits for each card, and we can start the
straight at any one of 10 cards (A through 10).}

\ppart\pts{5} %
A \emph{straight flush} is a set of five cards that is both a straight
and a flush: 5 cards in a row, all the same suit.  How many are there?

\solution{\textbf{Solution: }
$4\cdot 10$}

\ppart\pts{5} %
How many 5-card sets are either a straight \emph{or} a flush (or
both)?

\solution{\textbf{Solution: }
Inclusion-exclusion: $4^5\cdot 10 + 4\binom{13}{5} - 4\cdot 10$}

\eparts


% ps8 : f95 : 3
\problem\pts{10} \textbf{Counting}

Consider placing $n$ distinguishable books on $r$ distinguishable
shelves.

\bparts 

\ppart\pts{5} If the order of books on each shelf doesn't matter, how many
distinct placements are there?

\solution{\textbf{Solution: }
Product rule: $r$ shelves for each of $n$ books, so $r^n$.}

\ppart\pts{5} If order on the shelf matters, how many distinct placements
are there?

\solution{\textbf{Solution: }
For the first book there are $r$ choices. For the next book
there are $r+1$ choices since we can think of the first book as
splitting the shelf it is put on into two shelves. Similarly for the
third book there are $r+2$ choices. In this way we see that the
total number of ways, by the product rule, is $r\times (r+1) \times
(r+2) \ldots (n+r-1) $.}

\eparts

\problem\pts{10} \textbf{Order of Growth}

\bparts

\newcommand{\kalg}{\ensuremath{\mathbb{A}}}

\ppart\pts{3} From lecture, we know that any comparison-based sorting
algorithm \kalg{} must take $\Omega(n\log n)$ steps on $n$ elements.
Which one of the following is a consequence of this fact?

\begin{enumerate}
\item There is some constant $c>0$ for which all executions of \kalg{}
  will perform exactly $cn\log n$ steps.
\item There is some constant $c>0$ for which all executions of \kalg{}
  will perform at least $cn\log n$ steps.
\item\label{OG:ANS} There is some constant $c>0$ for which some
  executions of \kalg{} will perform at least $cn\log n$ steps.
\item There is some constant $c>0$ for which all executions of \kalg{}
  will perform at most $cn\log n$ steps.
\item There is some constant $c>0$ for which some executions of
  \kalg{} will perform at most $cn\log n$ steps.
\end{enumerate}

\solution{\textbf{Solution: }
\ref{OG:ANS} is the correct answer.  $\Omega$-notation
deals only with worst-case lower bounds; $\Omega(n\log n)$ is a lower
bound on the number of steps required for the
\textit{worst-case} input to \kalg{}.
}

\ppart\pts{3} Prove that $10n^2=O(n^3)$.

\solution{\textbf{Solution: }
$10n^2\leq c\cdot n^3$ for all $n\geq 1$ when $c\geq 10$, so
the theorem follows.}

\ppart\pts{4} Prove that $n^3$ is not $O(10 n^2)$.

\solution{\textbf{Solution: }
Assume $\exists c$ such that for all $n>N$, $n^3 < c\cdot
10n^2$. But this implies that $n^3/n^2 = n < 10c = c\cdot 10n^2/n^2$,
which is not true for any $n\geq 10c$, so it is not true for all
$n>N$.  This is a contradiction.}

\eparts

\problem\pts{10} \textbf{Summations}

\begin{problemparts}

\ppart\pts{5} Determine the closed-form expression for the summation:

\[ \sum_{k=0}^{\infty} \sum_{j=0}^{\infty} x^{k + j} y^{k - j}\]

\solution{\textbf{Solution: }
Rearrange:
\begin{eqnarray*}
\sum_{k=0}^{\infty} \sum_{j=0}^{\infty} x^{k + j} y^{k - j}
& = & \sum_{k=0}^{\infty} \sum_{j=0}^{\infty} x^k x^j y^k y^{-j} \\
& = & \sum_{k=0}^{\infty} x^k y^k  \sum_{j=0}^{\infty} x^j y^{-j} \\
& = & \left(\sum_{k=0}^{\infty} (xy)^k
\right)\left(\sum_{j=0}^{\infty} \left(\frac{x}{y}\right)^j\right) \\ 
& = & \frac{1}{1-xy}\cdot \frac{1}{1-x/y}
\end{eqnarray*}
when $|xy|<1$ and $|x/y|<1$.
}

\ppart\pts{5} Prove a tight asymptotic bound ($\Theta$) for the expression:

\[
\sum_{k=2}^n \frac{1}{k\ln k}
\]

{\bf Hint:} ${\displaystyle \frac{1}{x \ln x} = \frac{d}{dx}\ln\ln x}$

\solution{\textbf{Solution: }
$\sum_{k=2}^n \frac{1}{k\ln k} = \sum_{k=2}^n
\frac{d}{dk}\ln\ln k$, so we use the integral method:
\begin{center}
\begin{math}
\begin{array}{r@{\ \leq\ }c@{\ \leq\ }l}
\int_2^n\frac{d}{dk}\ln\ln k\ dk
& \sum_{k=2}^n \frac{d}{dk}\ln\ln k
& \int_2^n\frac{d}{dk}\ln\ln (k+1)\ dk \\
%
\ln\ln k|_2^n
&& \ln\ln (k+1)|_2^n \\
%
\ln\ln n - \ln\ln 2
&& \ln\ln (n+1) - \ln\ln 3 \\
%
\ln\ln n - \ln\ln 2
&& \ln\ln (n+1)
\end{array}
\end{math}
\end{center}
In the limit as $n\rightarrow \infty$, the left term is dominated by
$\ln\ln n$, so it is lower bounded by $c\ln\ln n$ for some constant
$0<c<1$.  Thus, the center is $\Omega(\ln\ln n)$ and $O(\ln\ln n)$.  }


\end{problemparts}


% ps7 : f95 : 6
\problem\pts{10} \textbf{Binomial Coefficients}

Prove that
\[ {\displaystyle \sum_{k=1}^n}k\left(\begin{array}{c} n\\ k\end{array}\right) = n2^{n-1} \]
\bparts

\ppart\pts{5} using a combinatorial argument.  {\bf Hint:} Consider
choosing a committee that is headed by a leader.

\solution{\textbf{Solution: }
Consider the number of ways of picking a team of size
  $k$ from a group of $n$ people and designating one of them captain.
  This can be done in $k{n\choose k}$ ways, for all $k =
  0,1,\ldots,n$. But the total number of ways of doing this can also
  be counted differently. First select the captain - $n$ ways - then
  select an arbitrary subset of the rest - $2^{n-1}$ ways. Hence the
  result follows.}

\ppart\pts{5} by finding a closed-form expression for ${\displaystyle
  \sum_{k=1}^n}\left(\begin{array}{c} n\\ k\end{array}\right)kx^k$ and
evaluating it at $x=1$.

\solution{\textbf{Solution: }
Differentiating 
\[(1+x)^n = {\displaystyle \sum_{k=0}^n {n\choose k}x^k}\]
we get
\[n(1+x)^{n-1} = {\displaystyle \sum_{k=1}^n k{n\choose k}x^{k-1}}\]
and evaluating it at $x=1$ we get the desired result.}

\eparts


\problem\pts{10} \textbf{Recurrences}

Consider the following recurrence:
\[ T(n)=2T(n/2)+n\log_2 n \]


\bparts

\ppart\pts{3} Perform two iterations of plug-and-chug to reveal a
pattern for this recurrence.

\solution{\textbf{Solution: } 
See below.}

\ppart\pts{7} %
Determine a tight asymptotic bound ($\Theta$) for this recurrence.
You may assume $n$ is a power of two if it is convenient.

\solution{\textbf{Solution: }
We expand:
\begin{eqnarray*}
T(n) &=& 2T(n/2) + n\log n \\
&=& 2^2T(n/2^2) + n\log\frac{n}{2} + n\log n \\
&=& 2^3T(n/2^3) + n\log\frac{n}{2^2} +
n\log\frac{n}{2} + n\log n \\ 
&\vdots& \\
%
&=& 2^{\log n}T(n/2^{\log n}) + n\left(\log\frac{n}{2^{\log n-1}}
+ \cdots + \log\frac{n}{2^2} + \log\frac{n}{2} + \log n\right) \\
% 
&=& \Theta(n) + n\left(\log 2+ \log 4 +\cdots
+ \cdots + \log\frac{n}{2} + \log n\right) \\
% 
&=& \Theta(n) + n\left(1+2+\cdots + \log n\right) \\
% 
&=& \Theta(n) + n\frac{(\log n)(1+\log n)}{2} \\
% 
&=& \Theta(n) + \Theta(n\log^2 n) \\
% 
&=& \Theta(n\log^2 n) \\
\end{eqnarray*}
}
\eparts


\problem\pts{10} \textbf{Recurrences}

The Millicent computer virus has been spreading on computers around
MIT.  Once a copy of Millicent enters a computer, it is copied to 2
new (uninfected) computers after one day, then to 3 new computers the
second day, and then detected and removed on the third day.
Millicent's creator installed Millicent on 2 computers on day 0 and 2
additional computers on day 1.

\begin{problemparts}


  \ppart\pts{3} Due to a tip from inside the FBI that Millicent might
  be of extraterrestrial origin, Frohike and Langley have been
  investigating the growth of the Millicent virus; however, they've
  gotten stuck.  Help them by stating a recurrence describing the
  number of computers \textbf{newly} infected on day $n$ for $n>1$.

\solution{\textbf{Solution: }
$T_n=2T_{n-1}+3T_{n-2}$}

\ppart\pts{4} Find a closed form for the recurrence you
stated in the previous part.

\solution{\textbf{Solution: }
The characteristic equation is $x^2-2x-3=0$, which has
roots at 3 and $-1$.  The solution is then of the form
\[T_n=A3^n+B(-1)^n \]  We plug in the given initial conditions:
%
\begin{eqnarray*}
T_0 = 2 &=& A + B \\
T_1 = 2 &=& 3A - B 
\end{eqnarray*}
%
Solving this system yields the coefficients $A=B=1$.  So, the closed
form for this recurrence is simply $T_n = 3^n + (-1)^n$.}

\ppart\pts{3} %
Fearing the efforts of the mighty Frohike and suave Langley,
Millicent's creator became frightened and decided to start installing
the virus on 4 new computers every day after day 1.  State a
recurrence for the revised problem and find a closed form solution for
the number of computers newly infected on day $n$.

\solution{\textbf{Solution: }
The general solution to the homogeneous recurrence is of the
form \[T_n=A3^n+B(-1)^n \] as above.  Now we need to find a particular
solution to the inhomogeneous recurrence.  Since the inhomogeneous
term is constant, we guess a constant solution $b$:
%
\[b = 2b + 3b + 5 \Longrightarrow b = - 1\]
%
Therefore, the inhomogeneous recurrence has the simple particular
solution $T_n=-1$.  We now need to determine the constants on the
complete solution
%
\[T_n=A3^n+B(-1)^n-1\] 
%
by plugging in the initial conditions and solving the resulting
system:
%
\begin{eqnarray*}
T_0 = 2 &=& A + B - 1 \\
T_1 = 2 &=& 3A - B - 1
\end{eqnarray*}
%
which has the solution $A=B=3/2$.  The closed form for this recurrence
is then 
%
\[T_n = \frac{3}{2}3^n + \frac{3}{2}(-1)^n - 1 \]
%
We can perform a sanity check to make us more confident of our answer:
\begin{center}
\begin{tabular}{l}
$T_2=2\cdot 2 + 3\cdot 2 + 4 = 14$ \\
$T_2=(3/2)3^2 + (3/2)(-1)^2 - 1 = 14$ \\ \hline
$T_3=2\cdot 14 + 3\cdot 2 + 4 = 38$ \\
$T_3=(3/2)3^3 + (3/2)(-1)^3 - 1 = 38$
\end{tabular}
\end{center}
}

\end{problemparts}

\problem\pts{10} \textbf{Countability}

\begin{problemparts}

  \ppart\pts{5} %
  A function $f: \nats \to \nats$ is \emph{strictly increasing} if
  $f(n+1)>f(n)$ for all $n$.  Prove that the set of such strictly
  increasing functions is uncountable.  \textbf{Hint:} Use
  diagonalization.

\solution{\textbf{Solution: }
To use diagonalization, we must assume that the set is countable, then
find a contradiction by performing two steps:
\begin{enumerate}
        \item[1.] Describe an \textbf{arbitrary} enumeration (ordered listing) 
              of \textbf{all} the elements in the set.
        \item[2.] Construct an item that is \textbf{in the set} but 
              \textbf{not equal} to any element of the enumeration.
\end{enumerate}

The emphasized elements are the crucial components; most false 
diagonalization proofs fail to satisfy one of those conditions.

The simplest diagonalization may be the following: List the functions in
some arbitrary enumeration $F$, where $F_i$ is the $i^{th}$ element of 
the list. Now, for any $F_i(x)$, the next value of the function, $F_i(x+1)$,
is either $1$ greater than $F_i(x)$ or more than $1$ greater than $F_i(x)$. 
We can now make a new function, $F_d$, where $F_d(x) = F_d(x-1)+1$ if 
$F_x(x) - F_x(x-1) > 1$ and $F_d(x-1)+2$ otherwise. $F_d$ must be in the 
set, since it is strictly increasing. However, $F_d$ cannot be equal to
any $F_i$, since it does not increase by the same amount from its value at
$i-1$ to its value at $i$.

The proof could also work if we define $F_d$ inductively by
$$F_d(x) = F_d(x-1) + (F_x(x) - F_x(x-1)) + 1.$$

In fact, an even simpler proof is to merely notice that the above 
analysis suggests a surjection from the set of increasing functions to 
the set of infinite binary strings, since every increase may either be 
$1$ or more than $1$:

\begin{equation}
\begin{array}{rccccccl}
F_0 & : & 2 & 3 &  7 & 8 & 9 & ... \\
F_1 & : & 6 & 7 &  10 & 13 & 22 & ... \\
F_2 & : & 2 & 4 &  8 & 9 & 16 & ... \\
F_3 & : & 1 & 5 &  6 & 7 & 40 & ... \\
\end{array}
\end{equation}

maps to:

\begin{equation}
\begin{array}{rcccccl}
F'_0 & : & 0 & 1 &  0 & 0 & ... \\
F'_1 & : & 0 & 1 &  1 & 1 & ... \\
F'_2 & : & 1 & 1 &  0 & 1 & ... \\
F'_3 & : & 1 & 0 &  0 & 1 &  ... \\
\end{array}
\end{equation}

This is an surjection to the set of infinite bit strings, which we have 
shown to be uncountable.
}

  \ppart\pts{5} %
  A function $f: \nats \to \nats$ is \emph{strictly decreasing} if
  $f(n+1)<f(n)$, for all $n$ such that $f(n)>0$, and $f(n+1)= 0$, for
  all $n$ such that $f(n) = 0$.  For example, the function $f$ could
  be $f(0)=5, f(1)=3, f(2)=0, f(3)=0, \cdots$.

  Prove that the set of such strictly decreasing functions is
  countable.  \textbf{Hint:} First prove that, for any $k \in \nats$,
  the set of strictly decreasing functions for which $f(0)=k$ is
  countable.

\solution{\textbf{Solution: }
Suppose $f(0)=k$. Then, since $f(x)$ decreases by at least $1$ for
each increment of $x$, $f(k)$ must be $0$. By the definition, 
$f(x) = 0$ for all $x > k$. 

We can describe each $f$ where $f(0) = k$ by noting which numbers
from $1$ to $k$ are in the range. (It can never be larger than $k$,
because the function is decreasing). In fact, this uniquely defines
each of the functions. We can view that as a finite bitstring of length
$k$, where position $i$ is $1$ if $i$ is in the range and $0$ otherwise.
Because $k$ can have any value, the decreasing functions map to finite
bitstrings of all lengths. This is thus an injection into the set of 
finite bitstrings. (Actually, a bijection, if we don't include the bit 
for $k$ itself). Since we have proven before that the set of finite
bitstrings is countable, the set of decreasing functions must also be 
countable.

We could have instead shown that functions of a given starting $k$,
there are only $2^{k-1}$ possible different functions, corresponding to
whether each number from $1$ to $k-1$ is in the range or not. Thus,
there are a finite number of decreasing functions for each starting $k$.
Since $k$ can only be any natural number, there are a countable number of
such sets comprising all of the decreasing functions. A union of 
countably-many finite sets is countable.

We could even have made a direct injection into the natural numbers or
finite bitstrings by mapping each $f$ to $f(0)$ 1's followed by 0 
followed by $f(1)$ 1's followed by 0 followed by 
$f(2)$ 1's followed by 0 followed by $\ldots$ for all $f(i) > 0$.
}

\end{problemparts}

\end{problems}

\end{document}






