\documentclass[11pt]{article}
\usepackage{calc,fancyhdr,lastpage}
\usepackage[hmargin=.75in,vmargin=1in,
            footskip=.5in,headsep=.5in-\headheight]{geometry}
\usepackage{amsmath,amssymb}

% Page layout.
\flushbottom  % stretch text to fill up page
\reversemarginpar  % margin notes on the left

% Common symbols and macros.
\input{macros-236}

% Headings.
\pagestyle{fancy}
\let\headrule\empty
\let\footrule\empty
\lhead{{\bfseries CSC\,236\,H1F}}
\chead{{\bfseries\large Homework Exercise \#\,4}}
\rhead{{\bfseries Fall 2009}}
\lfoot{{Dept.\ of Computer Science,
    University of Toronto (St.~George Campus)}}
\cfoot{{}}
\rfoot{{Page \thepage\ of \pageref{LastPage}}}


\begin{document}

\vspace*{-5ex}

\noindent
\strong{Worth:}  2\%
\hfill
\strong{Due:}  By 6pm on Wednesday 21 October

\vspace{2.5ex}

\noindent
For each question, please write up detailed answers carefully.
Make sure that you use notation and terminology correctly, and
that you explain and justify what you are doing.
Marks \strong{will} be deducted for
incorrect or ambiguous use of notation and terminology, and for
making incorrect, unjustified, ambiguous, or vague claims
in your solutions.

\noindent
Consider a function $f(n)$ that satisfies
the following recurrence relation:
\[
    f(n) =
    \begin{cases}
        1                                   & \text{if } n = 1
            \text{\bfseries\boldmath\ and $n = 0$},\\
        2 f(\floor{n/3}) + \ceil{\sqrt{n}}  & \text{if } n > 1.
    \end{cases}
\]
\begin{enumerate}


\item
    Apply the Master Theorem
    to find a tight bound on
    the value of $f(n)$---show your work, \ie,
    justify that the theorem applies and
    explain what values the various parameters take.


\item
    Apply Repeated Substitution
    to try to find an ``exact'' expression for
    the value of $f(n)$---show your work, \ie,
    explain what you are doing
    at each step of your solution,
    and why.


\end{enumerate}

\noindent
Recall the following facts about logarithms
(in your solution,
you may make use of any of these facts
without proof):
for all real numbers $b > 1$, $x > 0$, $y > 0$,
\begin{points}
\item  \(x^{\log_b y} = y^{\log_b x}\)
\item  \(\log_b(x^y) = y \log_b x\)
\item  \(\log_b(x y) = \log_b x + \log_b y\)
\item  \(\log_b(x / y) = \log_b x - \log_b y\)
\end{points}

\end{document}