\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}
\newcommand*{\len}{\operatorname{len}}

% To indicate number of marks for each question/subquestion.
\newcommand*{\worth}[1]
   {\mbox{}\marginpar{\raggedleft[#1]}\ignorespaces}

% Headings.
\pagestyle{fancy}
\let\headrule\empty
\let\footrule\empty
\lhead{{\bfseries CSC\,236\,H1F}}
\chead{{\bfseries\large Homework Assignment \#\,2}}
\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:}  8\%
\hfill
\strong{Due:}  By 6pm on \strong{Monday 2 November}

\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.
\begin{enumerate}


\item\worth{18}
    Consider the following ``ternary'' search algorithm.
    \begin{tabbing}
    MM\=MM\=MMMMMMMMM\=\kill
    \proc{TernarySearch}$(x,A,b,e)$:\\
    \>  \kw{if} $e \eq b$:\\
    \>  \>  \kw{if} $x \le A[b]$:\>  \kw{return} $b$\\
    \>  \>  \kw{else}:\>             \kw{return} $e + 1$\\
    \>  \kw{else if} $e \eq b + 1$:\\
    \>  \>  \kw{if} $x \le A[b]$:\>       \kw{return} $b$\\
    \>  \>  \kw{else if} $x \le A[e]$:\>  \kw{return} $e$\\
    \>  \>  \kw{else}:\>                  \kw{return} $e + 1$\\
    \>  \kw{else}:\\
    \>  \>  $c \gets (2 * b + e - 2) / 3$\quad\# integer division\\
    \>  \>  $d \gets (b + 2 * e - 1) / 3$\quad\# integer division\\
    \>  \>  \kw{if} $x \le A[c]$:\>       \kw{return}
                \proc{TernarySearch}$(x,A,b,c)$\\
    \>  \>  \kw{else if} $x \le A[d]$:\>  \kw{return}
                \proc{TernarySearch}$(x,A,c+1,d)$\\
    \>  \>  \kw{else}:\>                  \kw{return}
                \proc{TernarySearch}$(x,A,d+1,e)$
    \end{tabbing}
    Since $\log_3 n < \log_2 n$ for all $n > 1$,
    it would seem that this algorithm
    should be more efficient than binary search.
    However,
    the difference between $\log_3 n$ and $\log_2 n$
    is only a constant factor.

    In order to compare both algorithms,
    we need to analyze their running times
    more precisely.

    For your reference,
    here is the binary search algorithm
    for this question.
    \begin{tabbing}
    MM\=MM\=MMMMMMM\=\kill
    \proc{BinarySearch}$(x,A,b,e)$:\\
    \>  \kw{if} $e \eq b$:\\
    \>  \>  \kw{if} $x \le A[b]$:\>  \kw{return} $b$\\
    \>  \>  \kw{else}:\>             \kw{return} $e + 1$\\
    \>  \kw{else}:\\
    \>  \>  $m \gets (b + e) / 2$\quad\# integer division\\
    \>  \>  \kw{if} $x \le A[m]$:\>       \kw{return}
                \proc{BinarySearch}$(x,A,b,m)$\\
    \>  \>  \kw{else}:\>                  \kw{return}
                \proc{BinarySearch}$(x,A,m+1,e)$
    \end{tabbing}
    \begin{enumerate}

    \item\worth{6}
        Define a ``basic operation'' to be
        any comparison operator (``$\eq$'', ``$\le$'') or
        assignment operator (``$=$'')---all other
        operations and keywords are ignored.

        Let $T(n)$ denote the worst-case number of basic operations
        performed by \proc{TernarySearch}
        on any input of size $n$, and
        let $B(n)$ denote the worst-case number of
        basic operations performed by \proc{BinarySearch}
        on any input of size $n$.

        Write detailed and exact
        recurrence relations for $T(n)$ and $B(n)$.
        Justify that your recurrences are correct,
        from the algorithms.

    \item\worth{12}
        Determine
        which algorithm performs more basic operations
        in the worst-case,
        for any input of size
        {\bfseries\boldmath$n \ge n_0$
        (for some constant $n_0$
        to be determined as part of your solution)}, and
        write a detailed proof of your claim.
        Show all of your work.

    \end{enumerate}

\vfil


\item\worth{16}
    Suppose that you plan to buy a house and
    will need a mortgage of $A$ dollars
    at a monthly interest rate $I$ and
    a monthly payment $P$.
    Let $A_n$ denote the amount you have left to pay after $n$ months
    (in particular, $A_0 = A$).
    Assume that at the end of each month,
    you are first charged interest
    on all the money you owed during the month
    and then your payment is subtracted.
    \begin{enumerate}

    \item\worth{3}
        Write a recurrence relation for $A_n$,
        the amount owing after $n$ months,
        in terms of $A_{n-1}$, $I$, and $P$.
        Also include appropriate base case(s).
        Justify your recurrence briefly.

    \item\worth{5}
        Solve your recurrence relation so that
        you get a closed form formula for $A_n$
        in terms of $A$, $n$, $I$, and $P$.
        Show your work.

    \item\worth{8}
        Write a detailed proof
        that your formula in~(b) is correct.

    \end{enumerate}

\vfil


\item\worth{46}
    In this question
    we will examine two algorithms that
    return the two points closest to each other,
    given a list of points in the plane.
    The first algorithm is recursive and
    the second algorithm is iterative.
    Assume that \proc{Distance}$(p_1,p_2)$
    returns the Euclidean distance between
    any two points $p_1$ and $p_2$ and that
    $p_\infty$ is a sentinel value
    with the property that
    $\proc{Distance}(p_\infty, p_\infty) = \infty$.
    \begin{enumerate}

    \item\worth{23}
        Write a detailed proof of correctness
        for the following algorithm.
        \begin{tabbing}
        MM\=MM\=MM\=MM\=\kill
        $\proc{Find\_Closest\_Pair\_Rec}(A,e)$:\\
        \>  \# Precondition:  $A$ is a non-empty list of 2D points and
            $0 \le e < \len(A)$.\\
        \>  \# Postcondition:  Returns a pair of points which are
            the two closest points in $A[0\dotsc e]$.\\
        \>  \kw{if} $e < 1$:\quad
                \kw{return} $(p_\infty, p_\infty)$\\
        \>  $(p, q) \gets
            \proc{Find\_Closest\_Pair\_Rec}(A, e-1)$\\
        \>  $\var{min} \gets \proc{Distance}(p, q)$\\
        \>  \kw{for} $i \gets 0,\dotsc,e-1$:\\
        \>  \>  \kw{if} $\proc{Distance}(A[e], A[i]) < \var{min}:$\\
        \>  \>  \>  $\var{min} \gets \proc{Distance}(A[e], A[i])$\\
        \>  \>  \>  $p \gets A[e]$\\
        \>  \>  \>  $q \gets A[i]$\\
        \>  \kw{return} $(p, q)$
        \end{tabbing}

    \item\worth{23}
        Write a detailed proof of correctness
        for the following algorithm.
        \begin{tabbing}
        MM\=MM\=MM\=MM\=MM\=\kill
        $\proc{Find\_Closest\_Pair\_Iter} (A):$\\
        \>  \# Precondition:  $A$ is a non-empty list of 2D points and
            $\len(A) > 1$.\\
        \>  \# Postcondition:  Returns a pair of points which are
            the two closest points in $A$.\\
        \>  $\var{min} \gets \infty$\\
        \>  $p \gets -1$\\
        \>  $q \gets -1$\\
        \>  \kw{for} $i\gets 0,\dotsc,\len(A)-1$:\\
        \>  \>  \kw{for} $j \gets i+1,\dotsc,\len(A)-1$:\\
        \>  \>  \>  \kw{if} \proc{Distance}$(A[i], A[j]) < \var{min}$:\\
        \>  \>  \>  \>  $\var{min} \gets \proc{Distance}(A[i], A[j])$\\
        \>  \>  \>  \>  $p \gets i$\\
        \>  \>  \>  \>  $q \gets j$\\
        \>  \kw{return} $(A[p], A[q])$
        \end{tabbing}

    \end{enumerate}


\end{enumerate}

\end{document}