\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}{12 May 1998}{16}

\begin{center}
\Large{\bf Solution Sketch for Practice Problems}
\end{center}

\bigskip
{\bf 1.} Let $f$ and $g$ 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 Answer:} The above claim is not true for all functions $f$ and $g$.  Take
$f(n) = n$ and $g(n) = n^2$.  Clearly $f(n) \neq \Theta(g(n))$.  However,
$\log(f(n)) = \Theta(\log(g(n)))$ since $\log(f(n)) = \log n$ and $\log (f(n))
= 2\log n$.

Note that the above problem has an if and only if requirement.  While it is
true that $f(n) = \Theta(g(n))$ implies $\log (f(n)) = \Theta(\log(g(n)))$,
the converse is not necessarily true, as shown by the above example.

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

{\bf Answer:} Use Master Theorem, case 1 to obtain $T(n) =
\Theta(n^{\log_{10}11})$.

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

{\bf Answer:} Clearly $T(n) \ge 2n$.  Therefore $T(n) = \Omega(n)$.  Use the
recursion tree method for the upper bound.  The contribution of first level of
the tree is $2n$, the second level $\frac{8}{15}2n$, and in general,  the $i$th
level contributes at most $(\frac{8}{15})^{i-1}2n$.  On adding the
contributions together, we obtain a gemoetric series, yielding that
\[
T(n) \le 2n \cdot \frac{1}{1 - 8/15} = O(n).
\]
\end{itemize}

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

{\bf Answer:} The algorithm runs in $\lceil \lg k \rceil$ phases.  In the first
phase we group the $k$ lists into $\lfloor k/2 \rfloor$ pairs (and possibly
leaving one list unpaired).  Using the {\sc Merge} procedure of {\sc
Mergesort}, we merge each pair to obtain $\lceil k/2 \rceil$ sorted lists of
at most $2n$ elements each.  Since this phase performs at most $k/2$ merges,
the running time of this phase is $O(nk)$.  

We now repeat the process of grouping the lists into pairs and then pairwise
merging.  The $i$th phase performs at most $\lceil k/2^i \rceil$ merges, each
of two lists having at most $2^i n$ elements.  Thus the running time of phase
$i$ is $O(nk)$.  Since the phases are performed until we have one list
remaining, we obtain that the total number of phases is $O(\lg k)$.
Therefore, the total running time is $O(nk\lg k)$.

{\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 Answer:} The sequence consists of the consecutive integers $1$ through
$63$ in a specific order.  First, we insert $32$, then all multiples of $16$
that have not already been inserted, then all multiples of $8$ that have not
already been inserted, then all multiples of $4$ not already inserted, then
all multiples of $2$ not already inserted, and finally, all multiples of $1$
not already inserted.  That is, the sequence is:

(a) 32\\
(b) 16 48\\
(c) 8 24 40 56\\
(d) 4 12 20 28 36 44 52 60\\
(e) 2 6 10 14 18 22 26 30 34 38 42 46 50 54 58 62\\
(f) all the odd numbers from 1 to 63.

After inserting 32, we have one node.  After inserting 16 and 48, we end up
with a tree of height $0$ with the root being full.  After inserting the keys
in $(c)$ and $(d)$, we end up with a tree of height $1$ with all full nodes.
And finally, the keys in $(e)$ and $(f)$ yield a tree of height $2$ with all
full nodes.

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

{\bf Answer:} Let the length of multi-LCS of sequences $X_1[1..i_1]$,
$X_2[1..i_2]$, \ldots, $X_m[1..i_m]$ be given by $L[i_1,i_2, \ldots, i_m]$.
We need to find $L[n,n, \ldots, n]$.  The key idea is the following recurrence
for $L[i_1,i_2, \ldots, i_m]$
\[
L[i_1,i_2, \ldots, i_m]
= \left\{
\begin{array}{ll}
0 & \mbox{ if any of the $L_i$s is $0$},\\
1 + L[i_1 - 1, i_2 - 1, \ldots, i_m] & \mbox{ if $L[i_1] = L[i_2] = \ldots =
L[i_m]$},\\
\max_{1 \le j \le m} \{L[\ldots, i_{j-2}, i_{j-1}, i_j - 1, i_{j+1}, i_{j+2},
\ldots]\} & \mbox{ otherwise.}
\end{array}
\right.
\]
We can easily write an iterative bottom up calculation of array $L$ by using
$m$ for loops: $i_1$ going from $1$ to $n$, $i_2$ from $1$ to $n$, through
$i_m$ from $1$ to $n$.  While doing the calculation, we can also maintain an
array that will help us retrieve the actual solution (rather than just the
length).  

The running time of the algorithm is at most $(n+1)^m$ (the number of entries)
times $m$ (an upper bound on the time taken to compute each entry).  Therefore
the running time is $O(m(n+1)^m) = O(n^m)$, which is a polynomial since $m$ is
assumed to be a constant.
\end{document}

