\documentstyle[12pt,twoside,macpsfig]{article}
\input{macros-course}

\begin{document}

\handout{ps4}{Problem Set 4}{February 22, 1994}

\pset{4}
{\bf Reading:\ } Maurer \& Ralston: Sections 0.3-0.5, Chapters 2 and 3
of CLR (handout 14).

\medskip

The problems are divided into oral problems (prefix~``{\bf O}'') and
written problems (prefix~``{\bf W}'').\footnote{Thanks to
H. Wilf's {\em Algorithms and Complexity} for providing a number
of problems.}
The oral problems are due in tutorial on Monday, February 28.  
The written problems are due at the beginning of class on Tuesday,
March 1.  Remember to write up each problem on a separate page or
pages, with your name on each sheet.  

\medskip


\medskip

\begin{problems}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% \oproblem
% Suppose that $f:X \rightarrow Y$ is a bijection between sets $X$ and
% $Y$. Let $h:Y\rightarrow X$ be an ``inverse'' to $f$. That is
% $h\circ f = I_X$ where $I_X$ is the identity function on $X$. Show
% that $h$ actually exists and that $h$ is also a bijection.
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\oproblem
The following is a list of functions. Identify for each function
whether it is an injection, surjection, bijection (or none of the
preceding.) If the function is not a bijection, indicate subsets
of the domain and range so that the function is a bijection between
these subsets.

\begin{problemparts}

\problempart
$f: \reals\rightarrow\reals$ such that
\[ f:a \mapsto 3a \]

\problempart
$f:\reals\rightarrow\reals$ such that
\[ f:a \mapsto \sin(a) \]

\problempart
$f:\reals^{+}\rightarrow\reals$ such that
\[ f:a \mapsto \log(a) \]

\problempart
$f:\integers\rightarrow\integers$ such that
\[ f:a \mapsto \floor{{a\over3}} \]

% \problempart
% $f:\underbrace{\naturals\times\cdots\times\naturals}_{k {\rm\ times} } 
%    \rightarrow\{f| f:\naturals\rightarrow\naturals\}$ such that
% \[ f\Big( (i_1,\ldots,i_k) \Big) (j) = \Big| \{ i_l : i_l\ge j\} \Big| \]
% The set $\{f| f:\naturals\rightarrow\naturals\}$ is the set of functions
% from the naturals to the naturals.
% Recall that if $X$ is a finite set, then $|X|$ is the number of elements
% in $X$. 

\end{problemparts}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\oproblem
Let $X$ and $Y$ be finite sets. Let $f:X\rightarrow Y$ be a function.
Show that if $f$ is injective then $|X|\le |Y|$. Show that if $f$
is a surjection then $|X|\ge |Y|$. 

Prove that $|X| = |Y|$ iff there exists a bijection between $X$ and $Y$.

\goodbreak
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\oproblem
Determine whether 
each of the following statements about the asymptotic growth
of functions is true or false.

\begin{problemparts}

\problempart
$(x^2+3x+1)^3\sim x^6$

\problempart
${(\sqrt{x} +1)^3\over(x^2+1)} = o(1)$

\problempart
$ e^{1/x} = \Theta(1) $


\problempart
$  x^3(\log \log x)^2 = o(x^3 \log x) $


\problempart
$  \sqrt{1+\log x } = \Omega(\log \log x)$

\problempart
$ \sin(x) = \Omega(1) $

\problempart
$\sum_{j\le x} {1\over j^2} = o(1)$

\problempart
$\sum_{j\le x} 1 \sim x$

\end{problemparts}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\oproblem
The three sums listed below define three functions, $h_1,h_2,h_3$ on 
$x\in\reals^{+}$. 
\[ h_1(x) = \sum_{1\le j\le x} \left( {1\over j} + {3 \over j^2} + {4\over j^3}
    \right) \]

\[ h_2(x) = \sum_{1\le j\le x} \left(   \log j + j  
   \right) \]

\[ h_3(x) = \sum_{1\le j\le x} \left(  {1\over\sqrt{j}}
    \right) \]

For each sum, $h_i(x)$, find a closed form expression, $f_i(x)$, such
that $h_i(x)=\Theta\big( f_i(x) \big)$.

% \begin{problemparts}
% 
% \problempart
% Which of the following statements about $h_1$ are true?
% 
% (i)~$h_1(x)\sim\log(x) $ \hspace{.25in}
% (ii)~$h_1(x) = O(x)    $ \hspace{.25in}
% (iii)~$h_1(x)  \sim 2\log x    $     \hspace{.25in}
% 
% (iv)~$h_1(x) = \Theta(\log x)  $        \hspace{.25in}
% (v)~$h_1(x)  = \Omega(1)       $   \hspace{.25in}
% 
% \problempart
% Which of the following statements about $h_2$ are true?
% 
% (i)~$h_2(x)\sim  x/2 $      \hspace{.25in}
% (ii)~$h_2(x) = O(\sqrt{x})       $ \hspace{.25in}
% (iii)~$h_2(x)   = \Theta(\sqrt{x} \log x )       $ \hspace{.25in}
% 
% (iv)~$h_2(x) =    \Omega(\sqrt x)     $  \hspace{.25in}
% (v)~$h_2(x)       = o(\sqrt x )    $ \hspace{.25in}
% 
% \problempart
% Which of the following statements about $h_3$ are true?
% 
% (i)~$h_3(x)   =O(\sqrt x)       $      \hspace{.25in}
% (ii)~$h_3(x) = \Omega(x^{1/4})       $ \hspace{.25in}
% (iii)~$h_3(x)   = o(x^{1/4})       $ \hspace{.25in}
% 
% (iv)~$h_3(x)  \sim 2x^{1/4}       $  \hspace{.25in}
% (v)~$h_3(x)   =\Theta(x^{1/4})        $ \hspace{.25in}
% 
% \end{problemparts}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\oproblem
A function $f:\reals^{\ge0}\rightarrow\reals $ is called
\defi{asymptotically nonnegative} if there exists a constant $x_0>0$
such that $f(x)\ge0$ for all $x\ge x_0$.

There are six asymptotic symbols, namely
$O,o,\sim,\Theta,\Omega,\omega$. 
Consider these symbols as relations on the set of functions
$\{ f:\reals^{\ge0}\rightarrow\reals | f \hbox{\ is asymptotically
nonnegative}\}$.
Prove that $O$ is transitive. Namely, suppose 
$f,g,h:\reals^{\ge0}\rightarrow\reals $ are asymptotically nonnegative.
Show that if $f=O(g)$ and $g=O(h)$ then $f=O(h)$.

Identify which of the
reflexive, symmetric, antisymmetric, and transitive properties
each relation satisfies. Which of the asymptotic relations are
equivalence relations? You should be able to prove your statements.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\oproblem

 A function $f:\reals^{\ge0}\rightarrow\reals $ is called
 \defi{asymptotically positive} if there exists a constant $x_0>0$
% and a constant $\varepsilon\ge0$ 
 such that $f(x)> {0} $ % was {\ge \varepsilon}
 for all $x\ge x_0$.


Suppose $f,h:\reals^{\ge0}\rightarrow\reals$ are asymptotically 
positive functions. We'll show essentially
that there always exists a function $g$ with rate of growth
between that of $f$ and $h$. Specifically, prove that if
$f = o(h)$  then there exists a
function $g$ such that $f=o(g)$ and $g=o(h)$. Construct $g$
explicitly in terms of $f$ and $h$.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\oproblem
Prove that $\log(n!)\sim n\log n $.
Prove that $n! = o(n^n)$.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% \oproblem
% Prove that if $f,g:\reals^{\ge0}\rightarrow\reals$ are asymptotically
% positive functions, then $f(x)=\Theta \big(g(x)\big)$ iff $f(x)=O(g(x))$
% and $f(x)=\Omega(g(x))$.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\oproblem
A particular martial art has been 
studied by a set $U$ of people and mastered by a set $M\subset U$ of people.
Suppose there is a function $f:M\rightarrow M$ such that $m\in U$
was a student of $m'\in M$ if and only if $f(m')=m$. What can one
deduce about the way this martial art is taught? If you were told
that $f$ was injective, what else could you conclude?

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\oproblem  Let $f:A\rightarrow B$ and $g:B\rightarrow C$
 be injective functions.  Prove that
$g\circ f:A\rightarrow C$ is also injective.  
If $f$ and $g$ are both surjective, is $g\circ f$ necessarily surjective?
Prove your answer. What can you conclude about 
$g\circ f$ if $f$ and $g$ are bijections?
If $g\circ f$ is a bijection, what can you conclude about $g$ and $f$?

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\oproblem
Prove that
\[ 1+x \le e^x \le 1+x+x^2 \]
for $-1\le x\le 1$.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\oproblem
Let $f:\reals^{\ge0}\rightarrow\reals$ be asymptotically nonnegative.
Prove or disprove the following statement:
\[ f(x)=O\Big(g(x)\Big) \Longrightarrow {f(x)}^2=O\Big({g(x)}^2\Big) \]
As usual, if you disprove the statement, try to salvage as much as
possible.



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

\newpage

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\wproblem
Rank the following fourteen functions in increasing order of their rates of
growth. In particular, list them as $f_1,f_2,\ldots,f_{12}$ such
that $f_i = O(f_{i+1})$. Indicate whether $f_i = o(f_{i+1})$ or
$f_i = \Theta( f_{i+1})$.

\[ 2^{\sqrt{n}},\quad e^{\ln(n^3)},\quad  e^{\ln^2(n^3)},\quad 
 \ln(3^{n^{\ln (n^3)}}),\quad 
n^{3.01},\quad  2^{n^3},\quad  n^{1.6}\]
\[ \ln (n^3+1),\quad  \sqrt{n!},\quad  n^{3\ln n},\quad  
n^3\ln n,\quad  (\ln \ln n)^3,\quad  n^{.5}2^n,\quad  (n+4)^{12} \]

Briefly justify your ranking.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\wproblem
{\hspace{1in}}

\begin{problemparts}

\problempart
Find a function $f:\reals^{\ge0}\rightarrow\reals$ such that
$f(x)= O(x^{1+\varepsilon})$ for every constant $\varepsilon>0$,
but for which $f(x) \not= O(x)$. Prove that your function actually
satisfies these asymptotic properties.

\problempart
Let $a,b\in\reals^{+}$ be  constants.
Prove that if $a>1$, then $x^b=o(a^x)$.

\problempart
Let $a$ be a constant greater than $0$. 
Prove  that  $a^x=o((a+\varepsilon)^x)$ for any
constant $\varepsilon>0$.

\problempart
Let $f:\reals^{\ge0}\rightarrow\reals$ be an
asymptotically positive function. Fix a constant
$\varepsilon>0$.
Suppose further that $f(x)=O((2+\varepsilon)^x)$
It is not necessarily true that $f(x)=o((2+\varepsilon)^x)$.
% Prove this.

The statements 
``$f(x)=O((2+\varepsilon)^x)$ for all constants $\varepsilon>0$''
and
``$f(x)=o((2+\varepsilon)^x)$ for all constants $\varepsilon>0$''
are, however, equivalent. Prove this.



\end{problemparts}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% \wproblem
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\wproblem 
% In this problem you are asked to prove a version of Stirling's
% approximation to the factorial function. The basic approach will
% be to bound the natural log function, written $\log$, by two function,
% $f$ and $g$, that have natural geometric interpretations in terms
% of $\log n!$ and can
% be easily integrated. The result will be a bound on $\log(n!)$,
% which will (by exponentiation) bound $n!$.
% 
% \begin{problemparts}
% 
% \problempart Let $f$ and $g$ be functions from an interval $[a,b)$
% on the real line to $\reals$. Prove that if $f'(x)\ge g'(x)$ for
% all $a\le x <b$ and if $f(a)=g(a)$ then $f(x)\ge g(x)$  for
% all $a\le x <b$.
% 
% \problempart Prove the dual proposition. Namely, 
% let $f$ and $g$ be functions from an interval $(a,b]$
% on the real line to $\reals$. Prove that if $f'(x)\le g'(x)$ for
% all $x\in (a,b]$  and if $f(b)=g(b)$ then $f(x)\ge g(x)$  for
% all $x\in (a,b]$.
% 
% \problempart A function $f:(a,b)\rightarrow\reals$ is said to be
% {\defi convex} if for any points $a<x<y<b$ the  function
% $l:(x,y)\rightarrow\reals$ defined by 
% \[ l(z)= {z-y \over x-y} f(x) + {x-z \over x-y}f(y)\]
% satisfies $l(z)\le f(z)$ for all $z\in(x,y)$.
% 
% Assume that $f$ is (infinitely differentiable?) (taylorseries converges?) on 
% $(a,b)$. Prove that $f$ is convex on $(a,b)$ iff $f''$, the second derivative
% of $f$, is non-positive on $(a,b)$.
% 
% \problempart Define a function $f:[0,\infty)\rightarrow\reals$ as follows.
% For all  $m=1,2,3,\ldots$, if $m\le x \le m+1$ then let
% \[ f(x) = (m+1-x)\log m + (x-m) \log(m+1)\quad. \]
% Similarly, $g:[0,\infty)\rightarrow\reals$ is defined in pieces.
% For all  $m=1,2,3,\ldots$, if $m-1/2\le x < m+1/2$ then let
% \[ g(x) = {x\over m} -1 + \log m \quad.\] 
% 
% Graph $f$ and $g$.
% 
% \problempart
% Prove that for $x\in[0,\infty)$, $f(x)\le \log x\le g(x)$.
% 
% \problempart
% Prove  that 
% \[ \int_1^n g(x) = log(n!) + {1\over 8} - {1\over2} \log n -A \]
% for some positve number $A$ which might depend on $n$.
% 
% \problempart
% Prove  that 
% \[ \int_1^n f(x) = log(n!)  {1\over2} \log n \quad. \]
% 
% \problempart
% Prove that $\int \log u\, du = u \log u + C$.
% 
% \problempart
% Show that
% \[ {7\over 8} < \log(n!) - (n+{1\over2})\log n + n < 1\quad.\]
% 
% \problempart
% Conclude that
% \[ e^{7/8}\left(n\over e \right)^n \sqrt{n}<
%  n!<  e\left(n\over e \right)^n  \]
% for $n=2,3,4,5,\ldots$.
% Compare this to Stirling's formula that
% \[ \sqrt{2\pi} \left(n\over e \right)^n \sqrt{n} \sim
%  n!   \quad. \]
% 
% \problempart
% Use Stirling's formula to obtain an asymptotic approximation to
% $n \choose k$ as $n$ and $k$ both approach infinity. Use your
% approximation to obtain bounds on $n\choose k$ for all $n$ and
% $k$.
% 
% \end{problemparts}
% 
% 
% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% \wproblem
% In this problem you are asked to examine some properties of power
% series.
% 
% \begin{problemparts}
% 
% \problempart
% Let $I_X$ and $I_Y$ be the identity functions on the sets 
% $X$ and $Y$ respectively.
% Let $f:X\rightarrow Y$ and $g:Y\rightarrow X$ be functions.
% Show that $f\circ g=I_X$ does not imply that $g\circ f=I_Y$.
% 
% \problempart
% Prove that if $f\circ g=I_X$ and there exists $h$ such that
% $g\circ h=I_Y$ then $g\circ f=I_Y$ and $f=h$.
% 
% \problempart
% The \defi{formal power series} in $x$ with coefficients in
% $\reals$ are all series $\sum_{i\ge0} a_i x^i$ with $a_i\in\reals$.
% I.E. we don't worry about convergence. This set is denoted
% $\reals[[x]]$. Because formal power series do not need to converge,
% they are not functions on $\reals$. However, they can be treated 
% as functions. Let $x\reals[[x]]$ denotet the set
% \[ \left\{ sum_{i\ge0} a_i x^i \in \reals[[x]] : a_0=0 \quad.\right\}\]
% The notation arises from the fact that this set looks like what you
% should get from multiplying every formal power series by $x$.
% 
% A formal power series $f\in\reals[[x]]$ is a function from
% $x\reals[[x]]$ to $\reals[[x]]$, as follows: Let 
% $f=\sum_{i\ge0} a_i x^i$. Let $g\in x\reals[[x]]$ be
% $\sum_{i\ge1} b_i x^i$. Then $f(g)=\sum{i\ge0} c_i x^i$ is
% defined by letting $c_i$ be the coefficient of $x^i$ in
% \[ a_0 + a_1\left( \sum_{j=1}^i b_i x^i \right) +
%  a_2\left( \sum_{j=1}^i b_i x^i \right)^2 + \cdots +
%  a_i\left( \sum_{j=1}^i b_i x^i \right)^i \quad. \]
% 
% Show that a formal power series $f\in x\reals[[x]]$ is a function from
% $x\reals[[x]]$ to $x\reals[[x]]$.
% Is some formal power series in $x\reals[[x]]$ the an identity function,
% $I_{x\reals[[x]]}$, and if so which formal power series is it?
% 
% \problempart
% Given $g,h \in x\reals[[x]]$, show that $g\circ h=g(h)$.
% 
% \problempart
% Given $g=\sum_{i\ge1}a_i x^i \in x\reals[[x]]$, show that there exists 
% $h\in x\reals[[x]]$ such that $g\circ h=x$ iff
% the $a_1\ne0$. Conclude that $h\circ g=x$.
% 
% \problempart
% Formal power series can be multiplied by extending the distributive law
% as follows:
% \[  \left(\sum_{i\ge0} b_i x^i\right) \star \left(\sum_{j\ge0} c_j x^j\right)
% =\sum_{k\ge0} \left(\sum_{i=0}^k  b_i c_{k-i} \right) x^k \quad.\]
% Suppose $h$ and $g$ are formal power series which, when treated as
% functions on $\reals$ both converge absolutely in an interval $(a_0,a_1)$.
% It turns out that $h\star g$ treated as a function also converges on
%  $(a_0,a_1)$, and $g(a)h(a)=g\star h (a)$ for all $a\in(a_0,a_1)$.
% 
% Use this fact to prove that
% \[  \left(\sum_{i\ge0}  x^i\right) \star \left(\sum_{i\ge0} (-1)^i x^i\right)
%    = 1 \quad. \]
% Verify the above relation directly from the definition of $\star$.
% 
% \end{problemparts}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\end{problems}


\end{document}



