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

%\backwardscompatibility        % !! use for backwards compatibility
%\showsolutions                 % !! use to force solutions & skip query
%\hidesolutions                 % !! use to force no solutions & skip query
\renewcommand{\coursecopyrightnames}{Prof.~Albert~R.~Meyer}

\begin{document} 
\inclassproblems{5}                    % !! start the paper

\begin{problem}
We begin with two large glasses.  The first glass contains a pint of
water, and the second contains a pint of wine.  We pour 1/3 of a pint
from the first glass into the second, stir up the wine/water mixture in
the second glass, and then pour 1/3 of a pint of the mix back into the
first glass and repeat this pouring back-and-forth process a total of
$n$ times.
\begin{problemparts}
\problempart
Describe a closed form formula for the amount of wine in the first glass
after $n$ back-and-forth pourings.

\solution{The state of the system of glasses/wine/water at the beginning
of a round of pouring and pouring back is determined by the total amount
of wine in the first glass.  Suppose at the beginning of some round, the
first glass contains $w$ pints of wine, $0\leq w \leq 1$ and $1-w$ pints
of water.  The second glass contains the rest of the wine and water.

Pouring 1/3 pint from first glass to second leaves 2/3 pints of liquid and
$(2/3)w$ wine in the first glass, and 4/3 pints of liquid and 
$1 - (2/3)w$ wine 
in the second glass.  Pouring 1/3 pint back from second into first
transfers a proportion of (1/3)/(4/3) of the wine in the second glass into
the first.  So the round completes with both glasses containing a pint of
liquid, and the first glass containing
\[
(2/3)w + (1/4)(1- (2/3)w) = 1/4 + w/2
\]
pints of wine.  After one more round, the first glass contains
\[1/4 + (1/4 + w/2)/2 = 1/4 + 1/8 + w/2^2\]
pints of wine, and after $n$ more rounds
\[
\begin{array}{lll}
w/2^n + \Sigma_{i=1}^n (1/2)^{i+1} &=  w/2^n + (1/2)\Sigma_{i=1}^n
(1/2)^{i}\\
& = w/2^n + (1/2)(-1 + \Sigma_{i=0}^n (1/2)^{i})\\
& = w/2^n + (1/2)(-1 + (1 - (1/2)^{n+1})/(1 - 1/2))\\
& = w/2^n - 1/2 + 1 - (1/2)^{n+1}\\
& = w/2^n + 1/2 - (1/2)^{n+1}.
\end{array}
\]
Since $w=0$ initially, the pints of wine in the first glass
after $n$ rounds is
\[
1/2 - (1/2)^{n+1}.
\]
}

\problempart
What is the limit of the amount of wine in each glass as $n$ approaches infinity?
\end{problemparts}

\solution{
The limiting amount of wine in the first glass approaches 1/2 from below
as $n$ approaches infinity.  In fact, it approaches 1/2 no matter how the
wine was initially distributed.  This of course is what you would expect:
after a thorough mixing the glasses should contain essentially the same
amount of wine.
}
\end{problem}




\begin{problem}
Using the method described in lecture, a truck can travel across any size
desert if there is a large enough supply of gas at the border of the
desert.  Show that if there is a large enough supply of gas at the border,
a truck can also make a \emph{round trip} across any size desert.

\solution{
Given that it can make a one-way trip across any desert, it can make a
two-way trip by executing the one-way strategy for twice the desert width,
but turning around when it gets to the desert edge instead of continuing.

A considerably more efficient approach uses ideas similar to the one-way
crossing strategy: let $R_n$ be the distance a truck can travel into the
desert \emph{and return} on $n$ tanks of gas.  Clearly, $R_1 = 1/2$.

On $n+1$ tanks, the strategy is to have truck travel distance $x$ and back
$n$ times, leaving $1-2x$ tanks of gas at distance $x$ into the desert on
each trip.  It then makes one more one-way trip to $x$.  This leaves it
with $n(1-2x) + 1-x$ tanks of gas at position $x$.  Leaving an $x$th of a
tank so it can get back, if the remaining $(n(1-2x) + 1-x) -x =
(n+1)(1-2x)$ tanks equal $n$, it can execute the $n$-tank round trip
strategy from position $x$ and still return to the desert border.  So, letting
\begin{eqnarray}
(n+1)(1-2x) & = & n\\
x & = & 1/2(n+1)\\
R_{n+1} & = & R_n + x = R_n + 1/2(n+1).
\end{eqnarray}
Therefore,
\[
R_n = 1/2 (1 + 1/2 + 1/3 + \cdots + 1/n) = H_{n}/2.
\]
}
\end{problem}


\begin{problem}
Indicate which of the following holds for each pair of functions $(f(n),
g(n))$ in the table below.  Assume $k\geq 1$,
$\epsilon > 0$, and $c > 1$ are constants.
\begin{equation*}
\begin{array}{|cc|c|c|c|c|c|c|}
\hline
f(n) & g(n) & 
f = O(g) & f=o(g) & 
g = O(f) & g=o(f) & 
f = \Theta(g) & f\sim g 
\\\hline\hline
2^n & 2^{n/2} & & & & & & \\\hline
\sqrt{n} & n^{\sin n\pi/2} & & & & & & \\\hline
\log(n!) & \log(n^n) & & & & & & \\\hline
n^k & c^n & & & & & & \\\hline
\log^k n & n^\epsilon & & & & & & \\\hline
\end{array}
\end{equation*}

%\item $f=O(g)$
%\item $f=o(g)$
%\item $g=O(f)$
%\item $g=o(f)$
%\item $f = \Theta(g)$
%\item $f \sim g$
%\item none of the above.
%
%\begin{equation*}
%\begin{array}{|cc|}
%\hline
%f(n) & g(n) \\\hline\hline
%\log^k n & n^\epsilon \\\hline
%n^k & c^n \\\hline
%\sqrt{n} & n^{\sin n\pi/2} \\\hline
%2^n & 2^{n/2} \\\hline
%\log(n!) & \log(n^n) \\\hline
%\end{array}
%\end{equation*}

\solution{
\newcommand\y{\text{yes}}
\newcommand\n{\text{no}}
\[
\begin{array}{|cc|c|c|c|c|c|c|}
\hline
f(n) & g(n) & 
f = O(g) & f=o(g) & 
g = O(f) & g=o(f) & 
f = \Theta(g) & f\sim g 
\\\hline\hline
2^n & 2^{n/2} & 
\n & \n & \y & \y & \n & \n
\\\hline
\sqrt{n} & n^{\sin n\pi/2} & 
\n & \n & \n & \n & \n & \n
\\\hline
\log(n!) & \log(n^n) & 
\y & \n & \y & \n & \y &  \y
\\\hline
n^k & c^n &             
\y & \y & \n & \n & \n & \n
\\\hline
\log^k n & n^\epsilon & 
\y & \y & \n & \n & \n & \n
\\\hline
\end{array}
\]

Following are some hints on deriving the table above:

\begin{itemize}

\item[(a)] 
$\dfrac{2^n}{2^{n/2}}=2^{n/2}$ grows without bound as $n$
grows---it is not bounded by a constant.

\item[(b)] 
When $n$ is even, then $n^{\sin n\pi/2}=1$.  So, no constant times
$n^{\sin n\pi/2}$ will be an upper bound on $\sqrt n$ as $n$ ranges
over even numbers.  When $n \equiv 1 \bmod 4$, then $n^{\sin n\pi/2}=
n^1 =n$. So, no constant times $\sqrt n$ will be an upper bound on
$n^{\sin n\pi/2}$ as $n$ ranges over numbers $\equiv 1 \bmod 4$.

\item[(c)] 
\begin{eqnarray}
\log(n!) & = & \log \sqrt{2\pi n}\left(\frac{n}{e}\right)^n \pm
c_n\label{logS}\\
& = & \log n + n(\log n - 1) \pm d_n \label{logprod}\\
& \sim & n \log n\label{sim}\\
& = & \log n^n.\notag
\end{eqnarray}
where $a \leq c_n,d_n \leq b$ for some constants $a,b \in \reals$ and all
$n$.  Here equation~(\ref{logS}) follows by taking logs of Stirling's
formula,~(\ref{logprod}) follows from the fact that the log of a product
is the sum of the logs, and~(\ref{sim}) follows because any constant,
$\log n$, and $n$ are all $o(n \log n)$ and hence so is their.

\item[(d)] 
\emph{Polynomial} growth versus \emph{exponential} growth.

\item[(e)] 
\emph{Polylogarithmic} growth versus \emph{polynomial} growth. 

\end{itemize}

}
\end{problem}




% SOURCE:  FALL 00, TUTORIAL 7
% TOPIC:  Asymptotic notation
% in-class  SUBSTANTIALLY REVISED, F02 -- ARM

\begin{problem}
It is a standard fallacy to think that given $n$ quantities each of which
is $O(1)$, their sum would have to be $O(n)$, and so, for example $n^2$
would not be O(the sum).  But such a sum can grow as fast as $n^2$, or
$2^n$, or \emph{any} given function $g:\naturals \to \naturals^{+}$.

Given $g$, explain how to define a sequence $f_1,f_2,\dots$ of functions
from $\naturals$ to $\naturals$ such that
\[
f_i = O(1)
\]
for all $i\geq 1$, but
\[
g(n) = O(\sum_{i=1}^n f_i(n)).
\]

\solution{
Pick $f_i$ to be the constant function $g(i)$.  That is,
\[
f_i(n) \eqdef g(i),
\]
for all $i\geq 1$ and $n \ge 0$.  Since $f_i$ is a constant function, it
is $O(1)$.  But
\[
\sum_{i=1}^n f_i(n) \geq f_n(n) = g(n),
\]
so $g(n) = O(\sum_{i=1}^n f_i(n))$.}

\end{problem} 


\end{document}
