\documentstyle[12pt,handout]{article}
\begin{document}
\input{epsf}
\thispagestyle{empty}
\setlength{\parindent}{0pt}
\setlength{\parskip}{1.8ex}
\input{macros}
\input{courseMacros}

\newcommand{\heapsize}{\mbox{{\em heap-size}}}
\newcommand{\len}{\mbox{{\em length}}}
\newcommand{\power}{\mbox{{\sc Power}}}
\newcommand{\fastpower}{\mbox{{\sc FastPower}}}

\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 2001}{26 February 2001}{17}

\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.

\[ \log^2 n   \hs \hs 2^{\sqrt{n}} \hs \hs 100n^3 \]	

{\bf Answer:} The order, from slowest growing to fastest growing
function is:

\[ \log^2 n   \hs \hs 100n^3 \hs \hs 2^{\sqrt{n}} \]	

One can prove this by calculating the limits of the ratios.
\vfill 

\item[{\bf (b)}]
Indicate, with a brief justification, whether the following statement
is true:  The following recurrence relation can be solved by the
Master theorem.
\[T(n) = 2T(n/2) + n\lg n\]

{\bf Answer:} No, we cannot use the Master theorem (as taught in
class).  Even though, the form of the recurrence relation is the same
as in the Master theorem, none of the 3 cases apply.  We have $E = \lg
2/\lg 2 = 1$ and $f(n) = n \lg n$; thus, we are comparing $n$ and $n
\lg n$.  Case~1 does not apply since $n \lg n$ is a faster growing
function than $n^{1 - \eps}$ for any $\eps$.  Case~2 also does not
apply since $n\lg n \neq \Theta(n)$.  Finally case~3 requires $n\lg n
= \Omega(n^{1 + \eps})$ which requires $\lg n = \Omega(n^\eps)$, which
is not true.

\vfill

\item[{\bf (c)}] 
Indicate, with a brief justification, whether the following statement
is true:  The average of any set of $n$ numbers is always at least
half the median.  (You may assume that $n$ is odd.)  

{\bf Answer:} If all the numbers are nonnegative, then the statement
is true.  Let the numbers be $a_1$ through $a_n$.  Then, the average
equals $(\sum_i a_i)/n$.  Let the median be denoted by $m$.  Since at
least $\lceil n/2 \rceil$ numbers are greater than or equal to the
median, it follows that the average us at least $(\lceil n/2 \rceil
m)/n \ge m/2$.  (Note that here we are using the fact that all the
numbers are nonegative.)

If the numbers are allowed to be negative, then this is not true.
Consider the three numbers $-2, 0, 1$.  The average is $-0.5$ and the
median is $0$.  The above claim is not true.

\vfill
\end{itemize}

\newpage

{\bf Problem 2. (35 points) \hs} Derive a tight bound for the
following recurrence relation.  Assume that $T(n)$ is $\Theta(1)$ for
$n\le 4$.

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

{\bf Answer:} We solve using the recursion tree approach.  At the
root, we have a node with contribution $n$.  This has 3 children, two
corresponding to $T(n/4)$ and one corresponding to $T(n/2)$.  When we
unravel it to the second level, we get 2 nodes with contribution $n/4$
each and one node with $n/2$.  At the third level, we have 4 nodes
with contributions $n/16$, $4$ with $n/8$, and $1$ with $n/4$.  Each
level adds to exactly $n$.

The recursion tree is skewed.  The height along one side is $\log_4 n$
(since the parameter of the recurrence decreases by a factor of 4 each
level) and along the other is $\log_2 n$ (since the parameter of the
recurrence decreases by a factor of 2 each level).  Therefore, we get
$T(n) \le n \log_2 n$ and $T(n) \ge n \log_4 n = (n \log_2 n)/2$,
yielding $T(n) = \Theta(n \log n)$.

\newpage
{\bf Problem 2. (30 + 50 = 80 points) \hs} Consider the following
algorithm for calculating the $n$th power of a number $a$.

\begin{tabbing}
$\power(a, n)$\\
1. \= \algif\ \= $n = 0$\\
2. \> \> return 1\\
3. \> \algelse \\
4. \> \> return $a \times \power(a, n-1)$
\end{tabbing}

\begin{itemize}
\item[{\bf (a)}] Write a recurrence relation for the number of
multiplications performed by $\power$.  Solve the recurrence.

{\bf Answer:} Line 4 performs one multiplication and recurses from $n$
to $n - 1$.  Lines 1 and 2 indicate that $T(0) = 0$.  So we obtain the
following recurrence.
\[
T(n) = \left\{
\begin{array}{cc}
T(n-1) + 1 & n > 0\\
0 & n = 0
\end{array}
\right.
\]

By iteration or the recursion tree approach, we get $T(n) = n$.
\vfill

\item[{\bf (b)}] Describe a faster algorithm for the problem that
performs $O(\lg n)$ multiplications.  Justify the upper bound on the
number of multiplications performed by your algorithm.  ({\em Hint:}
Think divide-and-conquer.)

{\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.  So the
algorithm is:

\begin{tabbing}
$\fastpower(a, n)$\\
1. \= \algif\ \= $n = 0$\\
2. \> \> return 1\\
3. \> \algelse \\
4. \> \> $x = \fastpower(a, \lfloor n/2 \rfloor)$\\
5. \> \> \algif\ \= $n$ is odd\\
6. \> \> \> return $a \times x \times x$\\
7. \> \> \algelse\\
8. \> \> \> return $x \times x$
\end{tabbing}

The recurrence for the number of multiplications is $T(n) \le
T(\lfloor n/2 \rfloor) + 2$, and $T(0) = 0$.  Replacing $\lfloor n/2
\rfloor$ by $n/2$ and using the Master theorem, we get $T(n) = O(\lg n)$.

\vfill
\end{itemize}
\newpage

{\bf Problem 4. (40 points) \hs} You and your valentine each have a
long list of favorite restaurants.  On Valentine's Day, each of you
wants to go to a restaurant of your own liking.  Design an efficient
algorithm to determine whether there exists a restaurant that you both
like.  Assume that each list is of size $n$.  Analyze the worst-case
running-time of your algorithm.  The more efficient your algorithm is
in terms of its worst-case running time, the more credit you will get.

{\bf Answer:} We first note that names can be compared against each
other (alphebatically); so there is a notion of ordering among
restaurant names in the same way as there is a notion of ordering
among numbers.  Let the two lists be $M$ and $V$.  A simple
$\Theta(n^2)$ time algorithm can be obtained by checking for each pair
of elements $a \in M$ and $b \in V$ to see whether $a = b$.  Since
there are $n^2$ pairs, this takes $O(n^2)$ time in the worst-case.
Since we may have to go through all of the pairs to determine the
final result, the worst-case input will require $\Omega(n^2)$ time.
Thus, the running time of the algorithm is $\Theta(n^2)$.  But we can
do much better.  We consider two algorithms: a $\Theta(n\lg n)$-worst
case algorithm and a $\Theta(n)$ expected time algorithm using
hashing.

\begin{enumerate}
\item
We sort each of the lists $M$ and $V$ and then scanning through the
sorted lists for identical elements using a procedure similar to the
merge procedure of mergesort.

\begin{tabbing}
1. \= Sort $M$ and $V$ separately, both in nonincreasing order\\
2. \> $i = j = 1$\\
3. \> \algwhile\ \=  $i \le n$ and $j \le n$\\
4. \> \> \algif\ $M[i] = V[j]$ then \algreturn\ \algtrue\ and exit\\
5. \> \> \algelse\ if $M[i] > V[j]$, then $j = j + 1$ \algelse\ $i = i +
1$\\
6. \> \algreturn\ \algfalse
\end{tabbing}

For the running time of the algorithm, we note that the calculation of
list $S$ in step $1$ takes $O(n)$ time.  The sorting of the two lists
takes $O(n \lg n)$ time using heapsort or mergesort.  Finally the scan
through the two lists (steps 4 through 6) takes $O(n)$ time.
Therefore, the total running time of the algorithm is $O(n \lg n)$.

We can devise another $O(n \lg n)$ time algorithm by combining sorting
and binary search.  We first sort both the lists $M$ and $V$
separately.  Next, for each element $a \in M$, we check whether the
element $a$ belongs to $V$.  This step can be performed using binary
search.  If there does exist an $a \in M$ such that $a$ is in $V$,
then we return \algtrue; otherwise, we return \algfalse.  Sorting takes
$O(n \lg n)$ time.  Each binary search takes $O(\lg n)$ time.  Since
there are at most $n$ binary searches, the total running time is $O(n
\lg n)$.

\item
We hash the elements of $M$ into a table of size $n$, using a suitable
hash function.  Note that there may be collisions, but if the hash
function is chosen well, the expected time will be $\Theta(n)$.  Next,
for each element $x$ of $V$, we search whether $x$ is in $M$.  Since
the expected time for search is $\Theta(1)$ (constant), we obtain that
the total expected time is $\Theta(n)$.
\end{enumerate}


\newpage

{\bf Bonus Problem (20 bonus points) \hs} The $k$th {\em quantiles}\/
of an $n$-element set are the $k-1$ elements of the set that divide
the sorted set into $k$ equal-sized sets (assume that $n$ is a
multiple of $k$).  Give an $O(n \lg k)$-time algorithm to list the
$k$th quantiles of a set.  You may assume that all the elements of the
set are distinct.

{\bf Answer Sketch:} The $k$th quantiles are elements of rank $n/k$,
$2n/k$, \ldots, $(k-1)n/k$.  We first find the element of rank $\lceil
k/2 \rceil n/k$ using the linear-time selection algorithm.  This
splits the problem into two roughly equal-sized halves, and we need to
find $\lfloor k/2 \rfloor$ quantiles in each of those halves.  We thus
have $\lg k$ levels of recursion, each of which takes $O(n)$ time.
Therefore, the total running-time is $O(n \lg k)$.

  \end{document}
