\documentclass[12pt]{amsart}
\usepackage{amsmath} \usepackage{amsthm} \usepackage{amstext}
\usepackage{amsfonts} \usepackage{graphicx} \usepackage{latexsym}
\usepackage{epsfig}
% \input epsf
\def\p{\partial} \def\O{\Omega} \def\c{\cal} \def\a{\alpha}
\def\r{\rho} \def\e{\epsilon} \def\g{\gamma} \def\d{\delta}
\def\D{\Delta} \def\t{\theta} \def\T{\Theta} \def\N{\nabla}
\def\L{\Lambda} \def\l{\lambda} \def\m{\mu} \def\f{\frac}
\def\dis{\displaystyle} \def\s{\sigma}
\newcommand{\lx}{\left} \newcommand{\rx}{\right}
\setlength{\parindent}{0in} \setlength{\parskip}{\baselineskip}
\setlength{\textheight}{9.0in} \setlength{\textwidth}{6.5in}
\setlength{\topmargin}{0.0in} \setlength{\evensidemargin}{0in}
\setlength{\oddsidemargin}{0in}

\begin{document} %(
\baselineskip 24pt

\title{Problem Set 03}
% YOUR NAME GOES HERE under Author
\author{Your Name}
\maketitle

\begin{enumerate} %(

\item Let $f$, $g$, and $h$ all be bijective functions (so that
they have inverses) and they all map real numbers to real numbers.

\begin{enumerate} %( 
\item What is the inverse of $f \circ \lx(g \circ h\rx)$ in terms of
$f^{-1}$, $g^{-1}$, and $h^{-1}$?
% Answer below this line

\item Prove or disprove that $f + g + h$ is always bijective.
% Answer below this line

\end{enumerate} %)


\item This question deals with the $Mystery$ function which takes in
an ordered pair of 2 integers greater than 0, does the following
algorithm, and returns a single integer $i$.

\begin{tabular}{lll} %(
$Mystery\lx(\lx<n, m\rx>\rx)$ \\
$i := 0$ \\
{\bf while} $n > 0$  \\
\hspace{1cm}$p := m$ \\
\hspace{1cm}$n := n - 1$ \\
\hspace{1cm}{\bf while} $p > 0$ \\
\hspace{1cm}\hspace{1cm}$i := i + 1$ \\
\hspace{1cm}\hspace{1cm}$p := p - 1$ \\
{\bf return} i \\
\end{tabular} %)

\begin{enumerate} %( 
\item In more common language, what does $Mystery$ do?  I.e., what is
its return value, $i$, in terms of $n$ and $m$?
% Answer below this line

\item What's the big $O$ runtime complexity of $Mystery$ in terms of
$n$ and $m$?
% Answer below this line

\item What's the best runtime an algorithm can have to compute the
$Mystery$ function?
% Answer below this line

\end{enumerate} %)

\item Curious George has decided to answer his problem set 3 by doing
the following algorithm:

\begin{itemize} %(
\item George opens ps03.tex in his text editor and randomly presses keys
on his laptop for several minutes (some of the keys (like alt) do
nothing, and some, like the arrow keys, move the cursor around).
\item George then runs \LaTeX\ and compiles his program.  If he gets an
error, he deletes everything and starts over.
\item If his \LaTeX\ run is successful, George prints his ``solution
set'' out and takes it to HouCheng, who grades it for him almost
instantly.
\item If George's score is less than perfect, George starts over.
\end{itemize} %)

\begin{enumerate} %( 
\item What is the {\em average} big $O$ runtime complexity of George's
algorithm in terms of $n$, the number of characters in The Perfect
Solutions Set to Problem Set 3?
% Answer below this line

\item What's the {\em best case} complexity?
% Answer below this line

\item What's the {\em worst case} complexity?
% Answer below this line

\item  If George types 10 characters a second, about how long
would it take him to produce every sequence that's as long as the
phrase 
\begin{verbatim}
just_over_one_decillion_years 
\end{verbatim}
if his laptop has 27 characters (26 letters plus the space ``\_'')?

Note that among other sequences, George would type:
\begin{verbatim}
slfjqz_nnper_nnuiv__sfns_sdfl
sdc__qpirun_zocnweiufn_njf___
_sdc_qpirun__zocnweiufn_njf__
_monkey___hate__type_laptop__
all_work_and_no_play_make_geo
rge_dull_monkey_all_work_and_
just_over_one_decillion_years
\end{verbatim}
Please also note that I made an error in lecture: the term (in America, not
England) for $10^{33}$ is {\em decillion}, {\bf not} dectillion.
% Answer below this line

\end{enumerate} %)


\item BONUS: The {\em Ackermann} function maps $N \times N$ to $N$,
where $N$ is the set of positive integers.
\begin{itemize} %(
\item $A\lx(\lx<0, n\rx>\rx) = n + 1$
\item $A\lx(\lx<m, 0\rx>\rx) = A\lx(\lx<m - 1, 1\rx>\rx)$ if $m > 0$
\item $A\lx(\lx<m, n\rx>\rx) = A\lx(\lx<m - 1, A\lx(\lx<m, n - 1\rx>\rx)\rx>\rx)$ if $m > 0$ and $n > 0$
\end{itemize} %)

\begin{enumerate} %(
\item What is $A \lx(\lx<2,2\rx>\rx)$?
% Answer below this line

\item How many digits long is the decimal form of $A \lx(\lx<4,2\rx>\rx)$?
  (To get credit, you can either write the answer, or write pseudo-code
  for an algorithm that computes the Ackermann function.  To save
  trees, please {\em do not} write out the full decimal form of
  $A\lx(\lx<4,2\rx>\rx)$.)

% Answer below this line

% If you're using LaTeX, you can use the verbatim environment to write
% the pseudo-code.
% e.g.:
%
% \begin{verbatim}
% Ackerman (<m, n>)
% if m = 0 then return n + 1
% ...
% \end{verbatim}
\end{enumerate} %)

(Also, if you thought Ackermann's function grew quickly, check out
\begin{verbatim}
http://www.scottaaronson.com/writings/bignumbers.html 
\end{verbatim}
My favorite is the Busy Beaver.)

\end{enumerate} %)
\end{document} %)