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

\head{3390}{Analysis of Algorithms}{4 November 1998}{16}

\begin{center}
\Large{{\bf Midterm}} 
\end{center}

{\bf Instructions.}
\begin{Itemize}
\item
This is a 90 minute midterm, to be graded out of 100 points.  There are five
questions worth 20 points each.

\item
Read all the problems through first and attack them in the order that allows
you to make the most progress.

\item
Show your work, as partial credit will be given.  If you need extra space, use
the blank facing page.  

\item
Best of luck!
\end{Itemize}

\vfill

{\Large
\begin{center}
\begin{tabular}{||c|c|c||}\hline
Question & Score & Maximum \\ \hline
1 & & 20 \\ \hline
2 & & 20 \\ \hline
3 & & 20 \\ \hline
4 & & 20 \\ \hline
5 & & 20 \\ \hline
Total & & 100 \\ \hline
\end{tabular}
\end{center}
}

\vfill
\vfill

\begin{center}
{\bf Name:} {\vrule height0.4pt width3in}
\end{center}
\vfill
\vfill


\newpage

{\bf Problem 1. (20 points total)}
\begin{Itemize}
\item[{\bf (a) (6 points)}]
Prove or disprove the following statement:
\[
f(n) = \Theta((f(\sqrt{n}))^2)
\]
for all asymptotically positive functions $f(n)$.

\vfill

\item[{\bf (b) (7 points)}]
Give the asymptotic growth rate of the solution for the following recurrence.
Assume that $T(n)$ is $\Theta(1)$ for $n\le 2$.  

$T(n) = 3T(n/2) + n \lg n$.

\vfill

\vfill

\newpage
\item[{\bf (c) (7 points)}]
Give an upper bound for $T(n)$ in the following recurrence.  Assume that
$T(n)$ is $\Theta(1)$ for $n \le 5$.  Make your bound as tight as possible.

$T(n) = T(n/3) + T(2n/3) + n^2$.

\vfill

\end{Itemize}


\newpage

{\bf Problem 2. (20 points total)}

Let $A[1..n]$ be an array of $n$ unordered distinct integers, where $n$ is a
power of $2$.  Consider the following
randomized algorithm.
\begin{Enumerate}
\item
Select $k = 2\lg n$ numbers $i_1$, $i_2$, \ldots, $i_{k}$ independently and
uniformly at random from $[1..n]$.  (Note that the numbers need not be
distinct.)

\item
For $j \leftarrow 1$ to $k$, set $B[j]$ equal to $A[i_j]$.

\item
Find the median $m$ of $B$ using the algorithm {\sc Select} of text.

\item
Return $m$.
\end{Enumerate}
\begin{Itemize}
\item[{\bf (a) (2 points)}] Assuming that selecting a random number in $[1..n]$
takes constant time, what is the running time of the above algorithm?  

\vfill

\item[{\bf (b) (6 points)}] Let $S$ be any subset of $A$.  Let $X$ denote the
number of elements in $B$ that belong to $S$.  Determine $E[X]$ in terms of
$n$ and the size of $S$.  (Note that the elements in $B$ may not be all
distinct.  If an element in $S$ occurs $t$ times in $B$, then it will
contribute $t$ to the count $X$.  For example, if $B$ is the array $[5, 3, 4,
5, 3, 1]$ and $S = \{3, 1, 8\}$, then $X = 3$.)

\vfill
\vfill

\newpage

\item[{\bf (c) (12 points)}] Prove that with probability at least $1 - 2/n$,
the algorithm returns an element with rank greater than $n/12$ and at most
$11n/12$.  (You may use the inequality ${a \choose b} \le (3a/b)^b$ for all
positive $a$ and $b$ such that $b \le a$.)

\vfill \vfill
\end{Itemize}

\newpage

{\bf Problem~3. (20 points total)}

Let $X$ be an unordered set of $n$ distinct integers.  Let $Y$ be an unordered
set of $n$ integers (not necessarily distinct).  For each of the following
three parts, you are given an integer $Z$ and are asked to determine an $x$ in
$X$ and $y$ in $Y$ that satisfy a stated property.  For each part, briefly
describe your algorithm and justify its running time.
\begin{Itemize}
\item [{\bf (a) (6 points)}]
In $O(n)$ time, determine $x \in X$ and $y \in Y$ such that: 
\[
|x - y| \ge Z
\]
or determine that no two such numbers exist.

\vfill 

\item [{\bf (b) (7 points)}]
In $O(n \lg n)$ time, determine $x \in X$ and $y \in Y$ such that:
\[
|x - y| \le Z
\]
or determine that no two such numbers exist.

\vfill

\vfill

\newpage

\item[{\bf (c) (7 points)}]
In $O(n)$ expected time, determine $x \in X$ and $y \in
Y$ such that:
\[
|x - y| = Z
\]
or determine that no two such numbers exist.  ({\em Hint:}\/ Use hash tables.)

\vfill
\vfill
\end{Itemize}

\newpage

{\bf 4. (20 points total) }

Let $A[1..n]$ be an array of $n$ unordered distinct integers, where $n$ is a
power of $2$.  Given an integer $x$ (not necessarily in $A$), we define the
{\em level}\/ of $x$ in $A$ as follows.  Let $r(x)$ denote the number of
elements in $A$ that are less than or equal to $x$.  (Thus, if $x$ is in $A$,
then $r(x)$ is simply the rank of $x$.)  The level of $x$ in $A$ is the unique
integer $i$ such that $2^{i-1} < r(x) \le 2^i$.  For example, the level of the
smallest element of $A$ is $0$, while the level of the largest element of $A$
is $\lg n$.
\begin{Itemize}
\item[{\bf (a) (12 points)}] Design and analyze an efficient algorithm that
computes the level of every element in $A$.  Thus, your algorithm should take
as input the array $A$ and return an array $B[1..n]$ such that for $1 \le i
\le n$, $B[i]$ is the level of $A[i]$ in $A$.  Briefly justify the correctness
of your algorithm.

\vfill
\vfill

\newpage

\item[{\bf (b) (8 points)}] Now suppose that the elements in $A$ are given in
increasing order.  Thus, $A[1] < A[2] < \ldots < A[n]$.  Given any integer
$x$, design and analyze an efficient algorithm to determine the level of $x$ in
$A$.  Briefly justify the correctness of your algorithm.  ({\em Hint:}\/ A
running time of $O(\lg \lg n)$ is achievable.)  \vfill \vfill
\end{Itemize}

\newpage

{\bf 5. (20 points total)}

Suppose we want to maintain a dynamic set $S$ of integer ordered pairs.  Each
ordered pair is of the form $(x,y)$, where we refer to $x$ as the {\em first
coordinate}\/ and $y$ as the {\em second coordinate}.  Assume that the first
coordinates of all of the ordered pairs are distinct.

Devise a data structure that supports each of the following operations in
$O(\lg|S|)$ time.
\begin{Itemize}
\item
{\sc Insert}$(x,y)$: Add the ordered pair $(x,y)$ to the set $S$.  

\item
{\sc Delete}$(x,y)$: Delete a given ordered pair $(x,y)$ in $S$.

\item
{\sc FindMin}$(z)$: Let $S'$ denote the set of all ordered pairs in $S$ with first
coordinate less than or equal to $z$.  If $S'$ is empty, return {\sc Nil};
otherwise, return an ordered pair from $S'$ with minimum second coordinate
amongst all ordered pairs in $S'$.
\end{Itemize}
Briefly justify the correctness and running-time of the operations.

({\em Hint:}\/ Use an appropriately-augmented balanced binary search tree.)
\end{document}


