\documentclass[12pt]{article}
\input{macros-course}

\newcommand{\smallspace}{\ifshowsolutions\else\vspace{1in}\fi}
\newcommand{\mediumspace}{\ifshowsolutions\else\vspace{3in}\fi}
\newcommand{\largespace}{\ifshowsolutions\else\vspace{4in}\fi}
\newcommand{\nextproblem}{\newpage}


\askaboutsolutions

\ifshowsolutions
  \newcommand{\reading}[1]{}
%
  \newcommand{\handoutlabel}{pqsol2}
  \newcommand{\handouttitle}{Practice Quiz 2 Solutions}
  \newcommand{\handoutdate}{April 8, 2000}
  \newcommand{\collaboration}{}
  \newcommand{\titlebar}{\handout{\handoutlabel}{\handouttitle}{\handoutdate}}
%
\else 
  \newcommand{\reading}[1]{}
  \newcommand{\handoutlabel}{pquiz2}
  \newcommand{\handouttitle}{Practice Quiz 2}
  \newcommand{\handoutdate}{April 6, 2000}
  \newcommand{\duedate}{Never}
  \newcommand{\collaboration}{}
  \newcommand{\titlebar}{%
    \handout{\handoutlabel}{\handouttitle}{\handoutdate}
    \centerline{{\bf Due  Date: \duedate.}}
    \vspace*{\baselineskip}}
%
\fi

\renewcommand{\solution}[1]{\ifshowsolutions\par\textbf{Solution.} #1\fi}
\newcommand{\ksource}[1]{\ifshowsolutions\par\textsc{Source: #1}\fi}

\addtolength{\topmargin}{-.2in}
\setlength{\textheight}{9in}

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

\setcounter{page}{0}

%\newcommand{\pr}{\problem}

\begin{document}

\titlebar

\begin{problems}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%1
\problem
\bparts
\ppart Give tight ($\Theta$) bounds for 
\[{\displaystyle \sum_{i=1}^n \frac{1}{\sqrt{i}}}.\]

\solution{
\begin{eqnarray*}
{\displaystyle \int_1^n \frac{1}{\sqrt{x}} dx} & \leq {\displaystyle \sum_{i=1}^n \frac{1}{\sqrt{i}}} & \leq 1 + {\displaystyle \int_1^n \frac{1}{\sqrt{x}} dx} \\
{\displaystyle 2x^{\frac{1}{2}}|_1^n} & \leq  {\displaystyle \sum_{i=1}^n \frac{1}{\sqrt{i}}} & \leq 1 + {\displaystyle 2x^{\frac{1}{2}}|_1^n} \\
2\sqrt{n} - 2 & \leq {\displaystyle \sum_{i=1}^n \frac{1}{\sqrt{i}}} & \leq 2\sqrt{n} - 1 \\
{\displaystyle \lim_{n \rightarrow \infty} \frac{2\sqrt{n} - 2}{\sqrt{n}}} & \leq {\displaystyle \lim_{n \rightarrow \infty} \frac{\sum_{i=1}^n \frac{1}{\sqrt{i}}}{\sqrt{n}}} & \leq 1 + {\displaystyle \lim_{n \rightarrow \infty} \frac{2\sqrt{n} - 1}{\sqrt{n}}} \\
2 & \leq {\displaystyle \lim_{n \rightarrow \infty} \frac{\sum_{i=1}^n \frac{1}{\sqrt{i}}}{\sqrt{n}}} & \leq 2 \\
\end{eqnarray*}
That is 
\[ {\displaystyle \sum_{i=1}^n \frac{1}{\sqrt{i}}} = \Theta(\sqrt{n}).\]
}

\ppart Express the following in closed form 
\[ {\displaystyle \sum_{p=1}^{\infty} \sum_{q=p}^{\infty} x^py^q}.\]
(Note that the lower indices are not constants.)

\solution{
\begin{eqnarray*}
{\displaystyle \sum_{p=1}^{\infty} \sum_{q=p}^{\infty} x^py^q} & = {\displaystyle \sum_{p=1}^{\infty} x^py^p \sum_{q=p}^{\infty} y^{q-p}} & \\
 & = {\displaystyle \sum_{p=1}^{\infty} x^py^p \sum_{r=0}^{\infty} y^r} & \\
 & = {\displaystyle \left( \sum_{p=1}^{\infty} x^py^p  \right) \left( \sum_{r=0}^{\infty} y^r \right)} & \\
 & = \left( \frac{xy}{1-xy}\right)\left( \frac{1}{1-y}\right).
\end{eqnarray*}
}

\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%2
\problem 
I have $n$ one-dollar bills that I wish to donate  to $m$ charities.
\bparts
\ppart 
In how many ways can I do this if I don't care how much each charity gets?

\solution{
Simply insert $m-1$ bars into a string of $n$ one-dollar bills. Then the
$i$-th charity gets the money between bars $i-1$ and $i$. This gives you 
${n+m-1 \choose m-1 } $ ways to distribute the money.
}

\ppart 
In how many ways can I do this so that each charity gets at least \$ $10$?

\solution{
First give 10 dollars to each charity, then distribute the remaining
 $n-10m$ dollars as in part a. This gives you ${n+m-1-10m \choose m-1}=
{n-9m-1 \choose m-1}$ ways as long as $n\geq 10m$.
}

\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%3
\problem 
In how many ways can $5$ indistinguishable covered wagons, $4$ indistinguishable uncovered wagons and $1$
horse be arranged in a circle?

\solution{
This problem is just a permutation of a multiset, except that we need
to account for rotations of a circle being the same. This can be
thought of either as fixing one object, say the horse, and arranging
the wagons around it (${9\choose 5}$ ways), or counting the permutations
and dividing by $10$ to avoid overcounting the rotations
($\frac{1}{10}\frac{10!}{5!4!1!}$). Either way the answer is 126. The
most common mistake was to forget about overcounting the rotations.
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%4
\problem
How many $6$-digit decimal numbers are there that do not contain
``$123$'' or ``$456$'' as a subsequence? (for purposes of this problem
numbers may have leading $0$'s)

\solution{
Let
\begin{itemize}
\item $A$ be the set of all six-digit strings, using the digits
$\{0, 1, \ldots, 9\}$.
\item $B$ be the set of six-digit strings that contain the subsequence
$123$.
\item $C$ be the set of all six-digit strings that contain the subsequence
$456$.
\item $D$ be the set of all six-digit strings that do not contain 
$123$ or $456$.
\end{itemize}

We're interested in figuring out $| D |$.
Since $$D = A - (B \cup C),$$
and $B \cup C \subseteq A$,
we can use the inclusion-exclusion formula:
$$| D | = | A | - |B \cup C| = | A | - | B | - | C | + | B \cap C |.$$

First, $|A| = 10^6$, since we can put any of ten digits in each of
six places.  

Now, a string can contain $123$ in any of four positions; once this
position is chosen, we have $1000$ choices for the remaining positions.
However, this approach counts the string $123123$ twice, so 
the total size of $B$ is
$$| B | = 4(1000) - 1 = 3999.$$
By the same reasoning, we get
$$| C | = 3999.$$

Finally, there are only two strings in $B \cap C$, namely $123456$ 
and $456123$.  Thus,
$$| B \cap C | = 2.$$
Plugging this into our formula, we get
$$| D | = 10^6  - 3999 - 3999 + 2 = 992004.$$

{\em (Common Mistakes: A lot of people forgot about the double-counting
of $123123$ and $456456$, and so had $|B| = |C| = 4000$.  Some people also
argued that since $123$ can appear in one of only four places in the
string, $|B| = 4$.)}
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%5
\problem
Consider the following nuclear reaction. There is one particle of type
$1$ at time instant $1$. Each particle of type $i$ existing at time
$t$ undergoes fission to produce one particle of type $i+1$ and one of
type $i+2$ at time instant $t+1$.
\bparts 
\ppart 
Write and justify a recurrence for $f(i,t)$, the number of particles of type
$i$ at time $t$. (Make sure to include the base cases for your
recurrence.)

\solution{
Particles of types $i-2$ and $i-1$ at time $t-1$ give rise to
particles of type $i$ at time $t$ and this is the only way that
particles of type $i$ are formed at time $t$.
Hence we get the recurrence
\[ f(i,t) = f(i-1,t-1) + f(i-2,t-1), t > 1. \]
The base case is  
\begin{itemize}
\item $f(1,1) = 1$.
\item $f(i,1) = 0, -\infty \leq i \leq \infty, i \not= 1$.
\end{itemize}
}

\ppart 
Prove by induction that $f(i,t) = {t-1\choose i-t}$. (You do not need to reprove identities that were proven in class.)

\solution{
(Note: Let $a$ be any nonnegative integer and $b$ be any integer. In
what follows, we use the definition that ${a\choose b} =
\frac{a!}{b!(a-b)!}$ when $a\geq b \geq 0$ and otherwise ${a\choose b}
= 0$ when . Pascal's identity holds for this definition.)

 The proof is by induction on $t$. Let
$P(t)$ be
\[f(i,t) = {t-1\choose i-t}, \forall i.\]

Base Case. $P(1)$ is true since
\begin{itemize}
\item $f(1,1) = {0\choose 0} = 1$.
\item $f(i,1) = {0\choose i-1} = 0, -\infty \leq i \leq \infty, i \not= 1$.
\end{itemize}

Inductive step. Assume $P(t)$ is true. Consider $P(t+1)$. 
\begin{eqnarray*}
f(i,t+1) & = f(i-1,t) + f(i-2,t) & \mbox{ by the recurrence from part a)}\\
         & = {t-1\choose i-1-t} + {t-1\choose i-2-t} & \mbox{ by inductive hypothesis} \\
        & = {t\choose i-1-t} & \mbox{ by Pascal's identity} 
\end{eqnarray*}
Hence $P(t+1)$ is true. Thus $P(t)$ is true for all $t$ and we are done.
}

\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%6
\problem 
\bparts
\ppart Give tight ($\Theta$) bounds for $T(n)$. Assume that $T(n)$ is constant for $n \leq 10$.
 \[T(n) = 4T(n/2) + 6n.\]

\solution{
\begin{eqnarray*}
T(n) & = 4T(n/2) + 6n & \\
 & = 4^2T(n/2^2) + 6(n + n/2) & \\
 & = \ldots & \\
 & = 4^iT(n/2^i) + 6(n + n/2 + \ldots + n/2^{i-1}) & \\
 & = \ldots & \\
 & = 4^{\log_2 n}T(1) + 6(n + n/2 + \ldots + n/2^{\log_2 n \ -1}) & \\
 & = n^2T(1) + O(n) & \\
 & = \Theta(n^2)
\end{eqnarray*}
}

\ppart
Rank the following functions by order of growth; that is find an arrangement $g_1 = \alpha(g_2) = \alpha(g_3) = \ldots = \alpha(g_6)$ and state whether $\alpha$ is $o$ or $\Theta$ for each step.
\begin{itemize}
\item $n(\log_2 n)^5$
\item $n^3$
\item $n!$
\item $(n!)^2$
\item $n^n$
\item $3\cdot 8^{\log_2 n} + 4^{\log_2 n}$
\end{itemize}

\solution{
\[ n(\log_2 n)^5 = o(n^3) = \Theta(3\cdot 8^{\log_2 n} + 4^{\log_2 n}) = o(n!) = o(n^n) = o((n!)^2). \]
}

\eparts


\problem

%Prove or disprove:
%$f(n)=O(g(n))$ implies $\lg(f(n)) = O(\lg(g(n)))$, where $\lg(g(n)) > 0$ and
%$f(n) \geq 1$ for all sufficiently large $n$.

Prove or disprove: $f(n)=O(g(n))$ implies $\lg(f(n) = O(\lg(g(n)))$,
where $g(n)$ is nondecreasing, $g(1) > 1$ and $f(n) \geq 0$ for all
sufficiently large $n$.

\solution{ The theorem is true.  Assume $f(n)=O(g(n))$, so $\exists
  c,N\ \forall n\geq N\ f(n)\leq cg(n)$.  Choose appropriate $N>1$.
  Then, $\forall n\geq N$,
  \begin{displaymath}
    \begin{array}{crcl@{\ \ \ }l@{\ \ }c}
      & f(n) &\leq& cg(n) \\
      \Rightarrow & \log f(n) &\leq& \log cg(n) & (\mathrm{monotonicity}) \\
      &&=& \log c + \log g(n) \\
      &&\leq & k\log g(n) & \textrm{when\ }k=1+\frac{\log c}{\log g(1)} & (*) \\
    \end{array}
  \end{displaymath}
  So indeed, $\log f(n)=O(\log g(n))$.  The justification for the step
  marked $(*)$ is simply that, as $g(n)$ is nondecreasing and has some
  positive value (in this case at $n=1$), then for all $a>1$, $\log
  g(a)/\log g(1)\geq 1$, so
  \begin{eqnarray*}
    \log c+\log g(a) &\leq & \log c\cdot\frac{\log g(a)}{\log g(1)} + \log g(a) \\
    & = & k\log g(a)
  \end{eqnarray*}
  
}


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

\problem

Solve the following recurrence:
\[
f(1)=f(2)=1
\]
\[
f(n)-4f(n-1)+4f(n-2) = 3^n
\]


\solution{ The characteristic equation is $x^2-4x+4 = 0$, which has a
  double root at $2$.  The general solution to the homogeneous part is
  \[ f(n) = A2^n + Bn2^n \] We now have to determine a particular
  solution to the inhomogeneous recurrence, whose form we guess is
  $c3^n$; thus, we need to find the constant $c$:
  \begin{eqnarray*}
    c3^n-4c3^{n-1}+4c3^{n-2} &=& 3^n \\
    c\cdot 9-4c\cdot 3+4c&=& 9 \\
    (9-12+4)c &=& 9 \\
    c &=& 9
  \end{eqnarray*}
  so the inhomogeneous part is $9\cdot 3^n=3^{n+2}$.

  Now we know that the complete solution has the form
  \[ A2^n + Bn2^n + 3^{n+2} \]
  for which we need to find the constants given the boundary conditions.
  \begin{eqnarray*}
    f(1) = 1 &=& 2A + 2B + 27 \\
    f(2) = 1 &=& 4A + 8B + 81
  \end{eqnarray*}
  which resolves to $A=-6$, $B=-7$.  Thus, the complete
  solution is
  \[ f(n)=-6\cdot2^n - 7n2^n + 3^{n+2} \]

}

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

\problem
 
Give tight ($\Theta$) bounds for $T(n)$. Assume that $T(n)$ is constant for $n \leq 2$.

\bparts
\ppart $T(n) = 7T(n/3) + n^2$

\solution{Expand:
\begin{eqnarray*}
  T(n) &=& 7T(n/3) + n^2 \\
  &=& 7^2T(n/3^2) + 7(n/3)^2 + n^2 \\
  &=& 7^3T(n/3^3) + 7^2(n/3^2)^2 + 7(n/3)^2 + n^2 \\
  &\vdots& \\
  &=& 7^{\log_3 n}T(1) + 7^{\log_3 n-1}(n/3^{\log_3 n-1})^2 +
  \cdots + 7^2(n/3^2)^2 + 7(n/3)^2 + n^2 \\
  &=& 7^{\log_3 n}\Theta(1) + (7/9)^{\log_3 n-1}n^2 +
  \cdots + (7/9)^2 n^2 + (7/9)n^2 + n^2 \\
  &=& 7^{\log_3 n}\Theta(1) + \paren{\frac{1-(7/9)^{\log_3 n}}{2/9}} n^2 \\
  &=& n^{\log_3 7}\Theta(1) + \frac{9}{2} n^2 \left[ 1 - n^{\log_3(7/9)}\right] \\
  &=& \frac{9}{2} n^2 - \frac{9}{2} n^{n^2 + \log_3 (7/9)} + \Theta(1) n^{\log_3 7}
\end{eqnarray*}
Since $\log_3 (7/9) < 0$ and $\log_3 7 < 2$, it follows that $T(n) =
\Theta(n^2)$.
  }

\ppart $T(n) = T(2n/3) + T(n/4) + n$

\solution{%
  By expanding the recurrence we get:

  \begin{eqnarray*}
    T(n) 
    &=& n + T( (1/4) n ) + T( (2/3) n ) \\
    &=& n +(1/4) n + (2/3) n + T( (1/4)^2 n ) + 2 T( (1/4) (2/3) n ) + T( (2/3)^2 n ) \\
    &=& n + (1/4 + 2/3) n + (1/4 + 2/3)^2 n + (1/4 + 2/3)^3 n + \cdots
  \end{eqnarray*}

  It follows that:

  \begin{eqnarray*}
    n \sum_{}^{} \left( (1/4) + (2/3) \right)^{\log_{4} n}
    & \geq T(n) &
    n \sum_{}^{} \left( (1/4) + (2/3) \right)^{\log_{3/2} n} \\
    12 n \left( 1 - (11/12)^{\log_4 n}\right) 
    & \geq T(n) &
    12 n \left( 1 - (11/12)^{\log_{3/2} n}\right) \\
    12 n \left( 1 - n^{\log_4 (11/12)}\right) 
    & \geq T(n) &
    12 n \left( 1 - n^{\log_{3/2} (11/12)}\right) \\
    12 n - 12 n^{1 + \log_4 (11/12)} 
    & \geq T(n) &
    12 n - 12 n^{1 + \log_{3/2} (11/12)} \\
    \Omega(n)
    & = T(n) = &
    O(n) 
  \end{eqnarray*}

  It follows that $T(n) = \Theta(n)$.

%Guess and verify: Assume $T(n)=\Theta(n\log n)$.  We'll
%  prove the upper bound:
%  \begin{eqnarray*}
%    c(2n/3)\log(2n/3) + c(n/4)\log(n/4) + n &\leq& cn\log n \\
%    n\log n\cdot c\left(\frac{2}{3} + \frac{1}{4}\right) +
%    n\cdot \left[c\left(\frac{2}{3}\log\frac{2}{3}
%      +\frac{1}{4}\log\frac{1}{4}\right)+1\right] &\leq& \\
%  \end{eqnarray*}
%  which is true when $c>0$ and $c\left(\frac{2}{3}\log\frac{2}{3}
%    +\frac{1}{4}\log\frac{1}{4}\right)+1\leq 0$;
%  $\frac{2}{3}\log\frac{2}{3} +\frac{1}{4}\log\frac{1}{4}<0$, so this
%  is true when $c>-1/\left(\frac{2}{3}\log\frac{2}{3}
%    +\frac{1}{4}\log\frac{1}{4}\right)>0$.

%  Now for the lower bound:

}

\ppart $T(n) = 4T(n/3) + n$

\solution{Expand:
\begin{eqnarray*}
  T(n) &=& 4T(n/3) + n \\
  &=& 4^2T(n/3^2) + 4(n/3) + n \\
  &=& 4^3T(n/3^3) + 4^2(n/3^2) + 4(n/3) + n \\
  &\vdots& \\
  &=& 4^{\log_3 n}T(1) + 4^{\log_3 n-1}(n/3^{\log_3 n-1}) +
  \cdots + 4^2(n/3^2) + 4(n/3) + n \\
  &=& 4^{\log_3 n}\Theta(1) + (4/3)^{\log_3 n-1}n +
  \cdots + (4/3)^2 n + (4/3)n + n \\
  &=& 4^{\log_3 n}\Theta(1) + 3 \cdot \left((4/3)^{\log_3 n}-1\right)n \\
  &=& n^{\log_3 4} \Theta(1) + 3 \cdot \left(n^{\log_3 (4/3)} - 1\right) n \\
  &=& n^{\log_3 4} \Theta(1) + 3 n^{1 + \log_3 (4/3)} - 3 n^{\log_3 (4/3)} \\
  &=& n^{\log_3 4} \Theta(1) + 3 n^{\log_3 4} - 3 n^{\log_3 4 - 1} \\
  &=& \Theta\paren{n^{\log_3 4}}
\end{eqnarray*}
}

\eparts

\problem

Pick any set $A$ of ten numbers from 1 to 100.  Prove that there must
exist two distinct, non-empty subsets whose sums are equal.  E.g.,
consider the set $A=\set{51,11,81,68,73,87,23,29,25,94}$; in this
case, the subsets $\set{25,51,29}$ and $\set{94,11}$ both add to 105.
\textit{Hint:} Consider the number of subsets of a 10-element set.

\solution{Note that ten numbers between 1 and 100 have a maximum sum
  of $\approx 100$ (actually $100+99+98+\cdots+91$).  However, there
  are $2^{10}-1=1023$ non-empty subsets of a set of 10 numbers.  If we
  take our pigeonholes to be the possible sums and our pigeons to be
  the subsets, there are more subsets than possible sums, so at least
  one pigeonhole must have more than one pigeon.}


\end{problems}

\end{document}

% Local Variables: 
% mode: latex
% TeX-master: t
% End: 

