%revised 3/9/1pm ARM

\documentclass[12pt,twoside]{article}
\usepackage{amsmath}
\usepackage{graphics}
\input{macros-course}

\begin{document}
\pset{6}{March 9, 1999}{Tuesday, March 16}

\newcommand{\solution}[1]{}
%\newcommand{\solution}[1]{\bigskip {\bf SOL:}\\ #1}

\reading Fall 97 Lecture 10 notes.  Rosen \S5.1 \& \S5.3.  Tutorial 6 Notes.
(Material from Lecture 9 and Rosen \S1.7 and \S1.8 is also relevant.)

\begin{problems}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\problem {\bf (30 points)} 

Use the Master Theorem to find a $\Theta()$ bound on the solution to each
of the following recurrences:

\begin{enumerate}
\item[(a)]
$T(n) = 8T(\lfloor n/2\rfloor) + n^3$
\item[(b)]
$T(n) = 2T(\lfloor n/3\rfloor) + n$
\item[(c)]
$T(n) = 16T(\lfloor n/4\rfloor) + n\log n$
\item[(d)]
$T(n) = 2T(\lfloor n/4\rfloor) + \sqrt{n}$
\item[(e)]
$T(n) = 4T(\lfloor n/3\rfloor) + 1$
\item[(f)]
$T(n) = \pi*T(\lfloor n/\pi^3\rfloor) + n^{1/3}$
\end{enumerate}

\solution{
a. $(n^3)\log n$
\,\,\, (master theorem case 2)
\\
b. $n$
\,\,\, (master theorem case 3)
\\
c. $n^2$
\,\,\, (master theorem case 1)
\\
d. $\sqrt{n}*\log n$
\,\,\, (master theorem case 2)
\\
e. $n^{\log_3(4)}$
\,\,\, (master theorem case 1)
\\
f. $(n^{1/3})*\log n$
\,\,\, (master theorem case 2)
}

\problem {\bf (14 points)}

Consider the recurrence: $T(n) = 2*T(\lfloor\sqrt{n}\rfloor) + 1$

\begin{enumerate}
\item[(a)]

Make a substitution of the form $n = f(m)$ to turn this into a
recurrence to which one can apply the Master Theorem.
(Such recurrences are called ``divide and conquer'' recurrences).

\item[(b)] Give tight asymptotic bounds on $T(n)$.
(Hint: If you find it helpful to assume that $T(n)$ is a
non-decreasing function on positive integers, you may go ahead and
assume this without giving an argument why it is true.)

\solution{
Substitute $n = 2^m$ and get $U(m) = 2U(\lfloor m/2\rfloor) + 1$. Thus
$U(m) = \theta(m) = \theta(\log n)$


Define 
$U(m)=T(2^m)$, a function on integer $m$ only.

Then you argue that $U(m)=\theta(m)$.
This implies that 
$\exists_{c_1,c_2,m_0}\, \forall_{m\geq{m_0}}$
the following holds:

$$c_1 m \leq U(m) \leq c_2 m$$

because $T()$ is non-decreasing, we have:

$$T(2^{\lfloor \log_2 n\rfloor})
\leq 
T( n ) 
\leq 
T(2^{\lceil \log_2 n\rceil})$$

Now we can develop the left side of this equation:

$$T(n)\geq 
T(2^{\lfloor \log_2 n\rfloor})
=
U(\lfloor \log_2 n\rfloor)
\geq
c_1 \lfloor \log_2 n \rfloor 
\geq 
c_1 \log_2 n - c_1
\geq
c_1' \log_2 n
$$
for all $n\geq{n_0}$ for some $n_0$.

And similarly the right side:

$$T(n)\leq 
T(2^{\lceil \log_2 n\rceil})
=
U(\lceil \log_2 n\rceil)
\leq
c_2 \lceil \log_2 n \rceil 
\leq 
c_2 \log_2 n + c_1
\leq
c_2' \log_2 n
$$
for all $n\geq{n_0'}$ for some $n_0'$.

}

\end{enumerate}


\problem {\bf (30 points)}

Matt looks at merge sort algorithm from his 6.042 lecture and asks
"What is so special about 2 lists? Why can't I divide the list into
$k$ sublists to sort recursively and than merge these together?" He
calls his new algorithm the k-Merge Sort.

\begin{enumerate}

\item[(a)]
Show that by using an analogous procedure to the one used to merging
two lists, the worst case time to merge $k$ lists of total size $n$ is
$kn$.  

\solution{
$n$ elements, at most $k$ comparisons to find the next element}

\item[(b)]
Write down a recurrence for the k-Merge Sort.  

\solution{$T(n) = k*T(n/k) + kn$}

\item[(c)]
Show that the running time of k-Merge Sort is $kn\log_k(n)$. (Hint:
use the Plug and Chug method). For what value of k is the algorithm
fastest?

\solution{
$T(n) = k*T(n/k) + kn = k*(k*T(n/k^2) + k*(n/k)) + kn = k^2*T(n/k^2) +
2kn = k^i*T(n/k^i) + ikn = k^{\log_k(n)}*T(1) + {\log_k(n)}*kn =
\theta(kn\log_k(n))$

Fastest for minimal $kn\log_k(n)$, which is the same as minimal
$k/(\ln k)$, which is for $k=3$.}

\end{enumerate}

Matt thinks he can improve his algorithm by using divide-and-conquer
during the merge phase as well.  He suggests recursively merging k/2
of the sublists at a time and then using the old procedure to merge
the resulting two lists.

\begin{enumerate}

\item[(d)]
Using the notation $M(n,k)$ to denote the time it takes to merge $k$
lists of total size $n$ (each list has $n/k$ elements), Matt comes up
with the recurrence:

\[
M(n,k) = 2*M(n/2, k/2) + n
\]

Explain how he got this equation.

\solution{
Twice the time it takes to run this procedure recursively on the set
of $k/2$ lists, and $n$ time for mergining the two $n/2$-element lists that
resulting two lists.}

\item[(e)]
Show that $M(n,k)=\theta(n\log_2(k))$ for $k\leq{n}$.

\solution{
$M(n, k) = 2^i*M(n/2^i, k/2^i) + i*n = 2^{\log_2(k)}*M(n/k, 1) +
\log_2(k)*n = k*\theta(1) + n\log_2(k) = \theta(n\log_2(k))$ 
(if $k \leq n$)
}

\item[(f)]
What is the running time of k-Merge Sort using this new merging procedure?
How does it compare with the 2-Merge Sort previously done in lecture?


\solution{
New recurrence is $T(n) = k*T(n/k) + n*\log_2(k)$.  So $T(n) =
n*\log_2(k)*\log_k(n) = n*\log_2(n)$, independently of $k$.
}

\end{enumerate}

\problem {\bf (26 points)}

\noindent
Consider a set of record items, each carrying some data and a key.  We
define a {\em majority key} in such a set:


\begin{quote}
{\bf Definition:} The {\em majority key} of a set of $n$ records is a
key that occurs more than $n/2$ times.  

\noindent
(E.g.: $2$ is the majority key in a set of 3 records which are tagged,
consecutively, by keys $1$, $2$, and $2$.  On the other hand, in the
set of 4 records tagged by keys $1$, $2$, $3$, and $3$, there is no
majority key.)
\end{quote}

Consider the following algorithm for finding the majority key of a set of
records: If there is an even number of records, we pair adjacent items up
(first with second, third with fourth, etc.) and compare their keys.  If
they have the same key, we keep one of them, otherwise we throw them both
away.  We run this algorithm recursively on the resulting set.  If there
is an odd number of items in our set, we find the majority key of the set
containing all but the last item.  If there was no majority key than we
check if the key of the last record is the majority key by explicitly
counting how many times this key appears in the whole set.  We continue in
this fashion until we either get one record, in which case we check if its
key is in fact the majority key --- again by counting how many times this
key appears in the original set --- or we end up with no items, in which
case we conclude that there was no majority key.

\begin{enumerate}

\item[(a)]
Prove that if there is a majority key in the initial set of records
then this algorithm terminates with a record item carrying that key.
(Hint: Find an invariant that is preserved at every stage.  Consider
the even and odd cases separately.)

\solution{

Case 1: Even number of elements $= 2k$.  Element t occurs at least
$2k+1$ times.  After we pair the elements into k pairs, suppose
l pairs have two different elements and $k-l$ pairs have two
same elements.  Of the l different pairs, there is at most 1 t in
each pair, therefore at most l t's are taken away.  Hence, the same
elements have at least $k-l+1$ t's out of $2k-2l$ elements.  So, t is
a majority element now and it still will be after dividing the number
of elements by 2.

Case 2: Odd number of elements $=2k+1$.  If the last element is not t,
then t occurs $k+1$ times in the first $2k$, i.e. t is a majority
element of the first $2k$ and we can see case 1.

If the last element is t, than t may not be a majority element of the
first $2k$, but the first $2k$ can have no other majority element so
the algorithm will return either t or no majority, and in the latter
case we discover t is the majority element in the checking phase.}

\item[(b)]
Write down a recurrence for worst-case time this algorithm takes.  For
this part assume that the size of the working set at every stage is
even.

\solution{
$T(n)=T(n/2)+n/2$
}

\item[(c)]  
Solve the recurrence you wrote down in part (b) to obtain an
asymptotic time bound (theta) for worst-case running time.  (We are
interested in the {\em order} of growth, not the exact constant.)

\solution{
$T(n)=T(n/2)+n/2=T(n/4)+n/4+n/2=...=\theta(n)$
}

\item[(d)]
Argue that this time bound also holds without the assumption that the
working set at each stage is even.

\solution{
If the set is odd, then
$T(n)=T(n/2)+n/2+n=T(n/2)+3/2n$
which comes down to $T(n)=3n=\theta(n)$}

\end{enumerate}
\end{problems}

\end{document}


5)  (optional, 10 points)

The running time of algorithm A is described by the recurrence
T(n) = 16 T(n/4) + n^2.  A competing algorithm A? has a running
time T?(n) = aT?(n/2) + n^2.  What values of a ensure that algorithm
A has a better time asymptotically?
