\documentstyle[12pt,handout]{article}
\begin{document}
\input{macros}
\input{epsf}
\thispagestyle{empty}
\setlength{\parindent}{0pt}
\setlength{\parskip}{1.8ex}
\input{/home/rraj/Courses/1390/W00/Syllabus/localmacros}
\newcommand{\hs}{\hspace{1em}}

\newcommand{\ins}{\mbox{{\sc Insert}}}
\newcommand{\del}{\mbox{{\sc Delete}}}
\newcommand{\search}{\mbox{{\sc Search}}}
\newcommand{\mini}{\mbox{{\sc Minimum}}}
\newcommand{\maxi}{\mbox{{\sc Maximum}}}
\newcommand{\suc}{\mbox{{\sc Successor}}}
\newcommand{\pred}{\mbox{{\sc Predecessor}}}
\newcommand{\subtreemin}{\mbox{{\sc SubtreeMin}}}
\newcommand{\rt}{\mbox{{\it root}}}

\head{1390}{Algorithms}{Winter 2000}{22 February 2000}{14}

\begin{center}
\Large{{\bf Sample Solution to Midterm}} 
\end{center}

{\bf Problem 1.  (3 $\times$ 15 = 45 points) \hs} 
\begin{itemize}
\item[{\bf (a)}] Arrange the following functions in order from the
  slowest growing function to the fastest growing function.  You may
  simply state the answer without any additional justification.

\[ \lg n \hs (\lg \lg n)^2 \hs \sqrt{n} \]

{\bf Answer:} $(\lg \lg n)^2 \hs \lg n \hs \sqrt{n} $.

The above ordering can be justified by calculating the limits of the
ratios, as $n$ tends to $\infty$.  For example, the limit of the ratio
of $\lg n$ to $\sqrt{n}$ as $n$ tends to be $\infty$ can be calculated
using the L'Hopital's rule:
\begin{eqnarray*}
\lim_{n \rightarrow \infty} \frac{\lg n}{\sqrt{n}} 
& = & \lim_{n \rightarrow \infty} \frac{2(\lg e) \sqrt{n}}{n}\\
& = & \lim_{n \rightarrow \infty} \frac{2(\lg e)}{\sqrt{n}}\\
& = & 0.
\end{eqnarray*}

\item[{\bf (b)}] A {\em max-heap\/} is a heap in which the value
  stored at every node is less than the value stored at the parent of
  the node.  Is it true that the minimum element in a max-heap is
  always stored at a leaf node?  Briefly justify your answer. (Assume
  that all the keys in the heap are distinct.)

  {\bf Answer:} True.  Every non-leaf node $x$ has at least one child,
  the key of which is less than the key of $x$.  Therefore, a non-leaf
  node $x$ can never contain the minimum element. 
  
\item[{\bf (c)}] For which of the three open-addressing schemes,
  namely, linear probing, quadratic probing, and double hashing, is
  the following statement true?  For any two distinct keys $k_1$ and
  $k_2$, if $h(k_1) = h(k_2)$, then the probe sequence for $k_1$ is
  the same as that for $k_2$.  Here, $h$ is the primary hash function.
  Briefly justify your answer. 
  
  {\bf Answer:} True for linear probing and quadratic probing, since
  their probe sequences are given by $h(k) + i \bmod m$ and $h(k) +
  c_1i + c_2i^2 \bmod m$, each of which is fixed, once $h(k)$ is
  fixed.  On the other hand, the probe sequence for double hashing is
  given by $h(k) + ih'(k) \bmod m$, where $h'$ is the secondary hash
  function.  Therefore, in double hashing, even if $h(k_1) = h(k_2)$,
  $h'(k_1)$ and $h'(k_2)$ may be different, thus yielding different
  probe sequences.
\end{itemize}

{\bf Problem 2. (30 + 30 = 60 points) \hs} 
\begin{itemize}
\item[{\bf (a)}] Derive a tight bound for the following recurrence
  relation.  Assume that $T(n)$ is $\Theta(1)$ for $n\le 3$.

\[ T(n) = T(n/2) + T(n/3) + 2n.\]

{\bf Answer:} When we write the recursion tree for the above
recurrence, we obtain a contribution of $2n$ from level $0$, $2n(5/6)$
from level $1$, $2n(5/6)^2$ for level $2$, and so on.  In general,
level $i$ contributes $(5/6)^i 2n$.  Therefore, total contribution is
at most $2n(1 + (5/6) + (5/6)^2 + \ldots)$, which is the sum of a
geometrically decreasing sequence.  Taking the sum over infinite terms
yields the upper bound $2n(1 - 5/6) = 12n$.  

For the lower bound, it is easy to see from the recurrence that $T(n)$
is at least $2n$.  Therefore, $T(n) = \Theta(n)$.

\item[{\bf (b)}]
Consider the following sorting algorithm.

\begin{tabbing}
{\sc New-Sort}$(A,p,r)$ \hs (to sort $A[p..r]$)\\
1. \= $n = r - p + 1$\\
2. \> If $n > 1$ \= then\\
3.\> \> Find elements $m_1$ and $m_2$ of rank $\lceil n/3 \rceil$ and $\lceil 2n/3 \rceil$, respectively\\
\> \> using the linear-time selection algorithm ({\sc Select})\\
4.\>\> Partition $A$ into three parts $A[p..q]$, $A[q+1..s]$, and $A[s+1..r]$ such that\\
\> \>  every element in $A[p..q]$ is at most $m_1$, every element in $A[q+1..s]$ is greater\\
\> \>  than $m_1$ and at most $m_2$, and every element in $A[s+1..r]$ is greater than $m_2$\\
5.\>\> {\sc New-Sort}$(A,p,q)$\\
6.\>\> {\sc New-Sort}$(A,q+1,s)$\\
7.\>\> {\sc New-Sort}$(A,s+1,r)$
\end{tabbing}

Derive and solve a recurrence for the worst-case running time of {\sc
  New-Sort} on an array of $n$ elements.  You may ignore floors and
ceilings in your calculation.  Furthermore, you may afssume that all
the elements in the input array are distinct.

{\bf Answer:} Lines~1 and~2 take $\Theta(1)$ time.  Line~3 is
$\Theta(n)$.  Partitioning (line~4) also takes $\Theta(n)$ time since
it can be performed by a single pass through the elements of
$A[p..r]$.  Finally, lines~5,~6, and~7 each take time $T(n/3)$
(ignoring floors and ceilings).  Therefore, the recurrence is $T(n) =
3T(n/3) + \Theta(n)$.

The recurrence can be solved by the master theorem.  $f(n) =
\Theta(n)$, and $n^{\log_3 3} = n$.  Therefore, case~2 applies,
leading to a $\Theta(n \lg n)$ bound.
\end{itemize}



{\bf Problem 3. (40 points) \hs} Suppose we are given positive integers $a$
and $n$ and asked to compute $a^n$, that is, the $n$th power of $a$.
The simplest algorithm performs $n - 1$ multiplications by computing
$a \times a \times \ldots \times a$.  Design a divide-and-conquer
algorithm that computes $a^n$ using $O(\lg n)$ multiplications.
Justify the running time of the algorithm.

{\bf Answer:} If $n$ is even, we can write $a^n = (a^{n/2})^2$.  If $n$ is
odd, we can write $a \times (a^{\lfloor n/2\rfloor})^2$.  Thus, we can reduce
a problem of size $n$ to a problem of size $\lfloor n/2 \rfloor$ and then at
most 2 additional multiplications.  Therefore $T(n) \le T(\lfloor n/2 \rfloor)
+ 2$, and we get $T(n) = O(\lg n)$.



{\bf Problem 4. (15 + 40 = 55 points) \hs} 

\begin{itemize}
\item[{\bf (a)}] Label the following binary tree with numbers from the set $\{6,
  22, 9, 14, 13, 1, 8\}$ so that it is a legal binary search tree.

\vspace{.1in}

\centerline{\epsfxsize=4in \epsffile{sbst.eps}}

\item[{\bf (b)}] Recall that all of the binary search tree operations studied in
  class, namely, \ins, \del, \search, \maxi, \mini, \suc, and \pred\ 
  take $O(h)$ time in the worst-case, where $h$ is the height of the
  binary tree.  In this exercise, we would like to augment the binary
  search tree in such a way that the operation \mini\ can be
  calculated in $O(1)$ time.
  
  We add a new field called $\subtreemin[x]$, which stores for each
  node $x$ the minimum key value among all of the nodes in the subtree
  rooted at $x$.  This way, we can perform $\mini[T]$ by simply
  returning $\subtreemin[\rt[T]]$.
  
  Describe how to modify the \ins\ and \del\ operations so as to
  maintain the $\subtreemin[\cdot]$ field and yet keep the running
  time of the operations to be $O(h)$ time.
  
  {\bf Answer:} For inserting key $k$, just go through the path as in
  regular insertion, and change the $\subtreemin[x]$ value at any node
  $x$ to $k$ if $k$ is smaller than $\subtreemin[x]$.  Finally, when a
  new (leaf) node is created with key $k$, initialize the
  $\subtreemin$ field for this node to be $k$.  This modification adds
  only a constant number of operations per level to the original
  insert algorithm; hence the running time is still $O(h)$.
  
  For deleting, we consider three different cases. If the deleted
  node, say $x$, is a leaf node, then we trace the path from $x$ to
  the root until we reach the first node $y$ such that $y$ is the
  right child of its parent.  During this traversal, we update the
  $\subtreemin$ value for each node traversed (until and including
  $y$) to be the key of the parent of $x$.
  
  If the node to be deleted, say $x$, has only one child, then we
  delete the node as usual and set its child, say $u$ to be a child of
  the parent of $x$.  Then, as in the above case, we trace the path
  from $u$ to the root until we reach the first node $y$ such that $y$
  is the right child of its parent.  During this traversal, we update
  the $\subtreemin$ value for each node traversed (until and including
  $y$) to be the $\subtreemin$ value in $u$.
  
  Finally, if the node to be deleted, say $x$, has both children, one
  approach is to delete the node and replace it by the predecessor,
  then set the $\subtreemin$ value for the replacement node to be the
  minimum of the predecessor key and the $\subtreemin$ value stored in
  the left child of $x$ in the original tree.
\end{itemize}
  
\end{document}

