\documentstyle[12pt,handout]{article}
\begin{document}
\input{macros}
\input{/home/rraj/Courses/3390/S99/macros/localmacros}
\thispagestyle{empty}
\setlength{\parindent}{0pt}
\setlength{\parskip}{1.8ex}
\newcommand{\num}[1]{\mbox{{\em num}}[#1]}
\newcommand{\numnoargs}{\mbox{{\em num}}}

\head{3390}{Analysis of Algorithms}{Spring 1999}{12 May 1999}{17}

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

\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 
While describing an algorithm, you may use any of the algorithms covered in
class or in the text as a subroutine.  You need to provide a proof of
correctness and/or an analysis of the running time only for those problems
where they are explicitly required.

\item
Best of luck!
\end{Itemize}

\vfill

{\Large
\begin{center}
\begin{tabular}{||c|c|c||}\hline
Question & Score & Maximum \\ \hline
1 & & 20 \\ \hline
2 & & 10 \\ \hline
3 & & 20 \\ \hline
4 & & 30 \\ \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.  (2 $\times$ 5 = 10 points)}\hs Derive an asymptotically tight
bound for each of the following recurrences.  Assume that $T(n)$ is
$\Theta(1)$ for $n\le 2$.

\begin{itemize}
\item[(a)]
$T(n) = T(n/3) + T(2n/3) + n^2$.

\vfill

\item[(b)]
$T(n) = 2T(n/2) + n \lg n$.

\vfill
\end{itemize}

\newpage

{\bf Problem 2. (10 points)} \hs Let $A[1..n]$ be a sorted array of $n$
distinct keys.  Derive an asymptotically tight bound on the expected running
time of binary search of a given key $x$ in $A$ assuming that $x$ is in $A$
and is equally likely to be any of the $n$ keys.

\newpage

\junk{
{\bf Problem 2.} Let $A[1..n]$ be an array of $n$ distinct integers arranged
in decreasing order.  That is, $A[1] > A[2] > \ldots > A[n]$.  It is easy to
see that the array also forms a heap since every element satisfies the heap
property.  Design an efficient algorithm that when given a key determines the
height of a given key $k$ in the heap.
}

{\bf Problem 3. (20 points)}\hs Given an unsorted list $A$ of $n$ distinct
numbers and a number $s$, devise an efficient algorithm to determine whether
there exist two numbers $x$ and $y$ in $A$ that add up to $s$.  What is the
worst-case running time of your algorithm?  Can you give a more efficient
algorithm if the list $A$ is given in sorted order?  Explain.  (The more
efficient your algorithms are in terms of their worst-case running time, the
more credit you will get.)

\newpage


{\bf Problem 4. (15 + 15 = 30 points)} \hs Suppose we are maintaining a
dynamic set $S$ of distinct keys using a 2-3-4 tree.  Further assume that in
addition to the search, insert, and delete operations, we would like to be
able to compute the {\em rank}\/ of a given key in $S$.  Recall that the rank
of a key $x$ in a set $S$ is the number of keys in $S$ with value less than or
equal to $x$.  In this problem, we investigate how to compute the rank of a
given key.
\begin{itemize}
\item[(a)] For a node $x$, let $\num{x}$ denote the number of keys located in
the subtree rooted at node $x$ (including the keys in $x$).  Describe how to
maintain the field $\num{x}$, for every node $x$, without affecting the
asymptotic performance of the search, insert, and delete operations.

\newpage

\item[(b)] Using the $\numnoargs$ field, give an $O(\lg n)$ time algorithm to
determine the rank of a given key $k$ in $S$, where $n$ is the number of keys
in $S$.  Assume that $k$ is in $S$.

\end{itemize}

\newpage

{\bf Problem 5. (20 points)} \hs Two baseball fans share a collection of $n$
baseball cards.  They have agreed on an integer value for each card, say
$x_1$, $x_2$, \ldots, $x_n$.  They would like to split the cards into two sets
such that the two sets are as close to each other in value as possible.

Design an algorithm that determines how to split the cards into two sets such
that the absolute difference between the total value of one set and the total
value of the other is minimized.  Your algorithm should run in $O(n T)$ time,
where $T$ is the sum of the $x_i$'s. ({\em Hint:} Use dynamic programming.)
\end{document}

