\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 \#\,3}}
\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 14 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 the following algorithm---it is not
a realistic algorithm for the task that it carries out,
but we are concerned only with its running time in this Exercise.
\begin{tabbing}
MM\=MM\=MM\=MM\=\kill
\>  $\proc{Sum}(A,b,e)$:\\
\>  \>  \kw{if} $b \eq e$:\\
\>  \>  \>  \kw{return} $A[b]$\\
\>  \>  \# The rest executes only when $b \neq e$.\\
\>  \>  $m \gets (b + e) / 2$ \\
\>  \>  $s \gets 0$\\
\>  \>  \kw{for} $i \gets m+1,\dotsc,e$:\\
\>  \>  \>  $s \opgets+ A[i]$\\
\>  \>  \kw{return} $s + \proc{Sum}(A,b,m)$
\end{tabbing}
\begin{enumerate}


\item
    Let $T(n)$ denote the worst-case running time of
    $\proc{Sum}$ on inputs of size $n$.
    Write a recurrence relation satisfied by $T$.
    Make sure to define $n$ precisely
    (as a function of the algorithm's parameters) and
    justify that your recurrence is correct
    (by referring to the algorithm).
    In particular,
    describe clearly what ``steps'' you are counting.

\item
    Write a detailed proof that $T(n) \in \Omega(n)$,
    based on your recurrence relation from the previous part.
    Note that you should \strong{not} attempt to
    ``solve'' the recurrence in order to
    answer this question---``solving'' the recurrence
    is done in order to know what function to use
    as a bound on $T(n)$, and
    we've already provided you with that function
    in this question.


\end{enumerate}

\end{document}