\documentstyle[11pt,handout]{article}
\begin{document}
\input{macros}
\input{/home/rraj/Courses/3390/S99/macros/localmacros}
\thispagestyle{empty}
\setlength{\parindent}{0pt}
\setlength{\parskip}{1.8ex}

\head{3390}{Analysis of Algorithms}{Spring 1999}{5 May 1998}{14}

\begin{center}
\Large{\bf Practice Problems for Midterm}
\end{center}

\bigskip
{\bf 1.} Let $f(n)$ and $g(n)$ be two asymptotically positive and
monotonically increasing functions.  Prove or disprove the following
statement: $f(n) = \Theta(g(n))$ if and only if $\log (f(n)) =
\Theta(\log(g(n)))$.

{\bf 2.} Solve the following recurrences:
\begin{itemize}
\item[(a)] 
$T(n) = 11\cdot T(n/10) +n/\log n$.

\item[(b)]
$T(n) = T(n/5) + T(n/3) + 2n$.
\end{itemize}

{\bf 3.} Design an $O(n \lg k)$ time algorithm to merge $k$ sorted lists of
$n$ elements each into a single sorted list of $nk$ elements.

{\bf 4.} Give a sequence of insert requests that when applied to an initially
empty 2-3-4 tree results in a 2-3-4 tree of height $2$ in which all of the
nodes (including the root) are full nodes; that is, all of the nodes have $3$
keys.

{\bf 5.} Let the multi-LCS problem be defined as follows.  The input is a set
of $m$ length-$n$ sequences $X_i$, $0 \le i < m$.  The output is a longest
sequence $Y$ such that $Y$ is a subsequence of every $X_i$.  Use dynamic
programming to develop an algorithm for the multi-LCS problem that runs in
polynomial time for any fixed constant $m$.

\end{document}

