\documentstyle[11pt,handout]{article}
\begin{document}
\input{macros}
\input{/home/rraj/Courses/1390/Syllabus/localmacros}
\newcommand{\hs}{\hspace{1em}}
\newcommand{\Hspace}{\hspace{1em}}

\thispagestyle{empty}
\setlength{\parindent}{0pt}
\setlength{\parskip}{1.8ex}

\head{1390}{Algorithms}{Winter 1999}{8 February 1999}{11}

\begin{center}
\Large{\bf Sample Solution to Problem Set 2}
\end{center}

\bigskip

{\bf 1.  Asymptotic Notation} (5 $\times$ 4 = 20 points) 

For each of the following statements, indicate whether it is true or
false.  Briefly justify your answers.
\begin{itemize}
\item[(a)] 
$n^{3/2} = O(n \lg n)$.

{\bf Answer:} False.  We will prove it by contradiction.  Let, if possible,
there exist positive constants $c$ and $n_0$ such that $n^{3/2} \le cn \lg n$
for all $n \ge n_0$.  This implies that $\sqrt{n} \le c \lg n$ for all $n \ge
n_0$.  Or, $\sqrt{n}/\lg n \le c_0$ for all $n \ge n_0$.  But, we have:
\[\lim_{n \rightarrow \infty} \frac{\sqrt{n}}{\lg n} = \lim_{n \rightarrow
\infty} \frac{n}{2\sqrt{n}} = \infty,\]
by using L'Hopital's rule.  This implies that the constant $c$ does not exist
leading to a contradiction.

\item[(b)]
Given that $T(1) = 1$, a valid solution to the recurrence $T(n) =
2T(n-1)$ is $T(n) = \Theta(2^n)$.

{\bf Answer:} True.  We use the recursion method.
\begin{eqnarray*}
T(n) & = & 2T(n-1) \\
& = & 2^2T(n-2)\\
& = & 2^iT(n-i)\\
& = & 2^nT(1)\\
& = & 2^n.
\end{eqnarray*}
Thus, $T(n) = \Theta(2^n)$ is a valid solution.

\item[(c)]
The statement ``The worst-case running time of algorithm $A$ is
$O(n)$'' implies the following: there exist positive constants $c$ and
$n_0$ such that for every input $I$ of size $n \ge n_0$, the running
time of $A$ on input $I$ is at most $c n$.

{\bf Answer:} True.  By the definition of the $O$-notation, the phrase ``the
worst-case running time of algorithm $A$ is $O(n)$'' implies that there exist
positive constants $c$ and $n_0$ such that the worst-case running time of $A$
on inputs of size $n$ is at most $cn$ for all $n \ge n_0$.  By the definition
of ``worst-case'', it follows that if the worst-case input of size $n$
requires at most $cn$ time then {\em every}\/ input of size $n$ requires at
most $cn$ time.  Therefore, there exist positive constants $c$ and $n_0$ such
that the the running time of $A$ on every input of size $n$ is at most $cn$
for all $n \ge n_0$.

\item[(d)]
The statement ``The best-case running time of algorithm $A$ is
$O(n)$'' implies the following: there exist positive constants $c$ and
$n_0$ such that for every $n \ge n_0$, there exists an input of size
$n$ for which the running time of $A$ is at most $c n$.

{\bf Answer:} True.  By the definition of the $O$-notation, the phrase ``the
best-case running time of algorithm $A$ is $O(n)$'' implies that there exist
positive constants $c$ and $n_0$ such that the best-case running time of $A$
on inputs of size $n$ is at most $cn$ for all $n \ge n_0$.  By the definition
of ``best-case'', it follows that there {\em exists}\/ an input of size $n$
that requires at most $cn$ time.  Therefore, there exist positive constants
$c$ and $n_0$ such that for all $n \ge n_0$, there exists an input of size $n$
for which the running time of $A$ at most $cn$.

\item[(e)]
The statement ``The worst-case running time of algorithm $A$ is
$\Omega(n)$'' implies the following: there exist positive constants
$c$ and $n_0$ such that for every input $I$ of size $n \ge n_0$, the
running time of $A$ on input $I$ is at least $c n$.

{\bf Answer:} False.  By the definition of the $\Omega$-notation, the phrase
``the worst-case running time of algorithm $A$ is $\Omega(n)$'' implies that
there exist positive constants $c$ and $n_0$ such that the worst-case running
time of $A$ on inputs of size $n$ is at least $cn$ for all $n \ge n_0$.  By
the definition of ``worst-case'', it follows that if the worst-case input of
size $n$ requires at least $cn$ time then there {\em exists}\/ an input of
size $n$ that requires at most $cn$ time.  It is not true, however, that all
of the inputs of size $n$ require at least $cn$ time.  Therefore, the
statement is false.

\end{itemize}

{\bf 2.}  Problem 7--1 (10 + 10 = 20 points)
\begin{enumerate}
\item[(a)] {\sc Build-Heap'} and {\sc Build-Heap} may return different heaps
on the same input.  Consider the input array $A = [1, 2, 3]$.  The routine
{\sc Build-Heap} only runs {\sc Heapify} on the node with value $1$ to obtain
the heap $[3, 2, 1]$.  On the other hand, {\sc Build-Heap'} first inserts the
element $2$ into the subarray $[1]$ to obtain the heap $[2,1]$ and then
inserts the element $3$ into the array $[2,1]$ to obtain $[3,1,2]$.  So the
two heaps obtained are different.

\item[(b)] We know that the {\sc Heap-Insert} operation takes $O(\lg k)$ time
on a heap of size $k$.  Since we have $n$ {\sc Heap-Insert} operations, each
running on a heap of size at most $n$, the total running time is $O(n \lg n)$.

We now prove a matching lower bound.  Consider the input $[1,2,\ldots,n]$;
that is, the elements are in increasing order.  In each of the $n$ {\sc
Heap-Insert} operation executed by {\sc Build-Heap'}, the element being
inserted is sent to the root of the binary tree.  That is, when element $i$ is
being inserted, then $\lfloor \lg i\rfloor$ comparisons are performed.
Therefore, the total running time is at least
\begin{eqnarray*}
\sum_{i = 2}^{n} \lfloor \lg i \rfloor & \ge & \sum_{i = 2}^{n} (\lg i - 1)\\
& \ge & (\sum_{i = \lceil n/2\rceil}^n \lg i) - n\\
& \ge & \frac{n}{2} \lg\left(\frac{n}{2}\right) - n\\
& = & \frac{n\lg n}{2} - \frac{3n}{2}.
\end{eqnarray*}
We would like to show that $(n\lg n)/2 - (3n)/2 = \Omega(n \lg n)$.  We do
this by selecting positive constants $c$ and $n_0$ such that $(n\lg n)/2 -
(3n)/2 \ge c n \lg n$ for all $n \ge n_0$.  Since we have $(n\lg n)/2$ on the
left hand side of the inequality, we need to pick $c < 1/2$.  Let us pick $c =
1/4$.  So we need to prove that $(n\lg n)/2 - (3n)/2 \le n\lg n/4$.  On
simplifying this, we obtain the condition that $\lg n \ge 6$, which translates
to $n \ge 64$.  Thus, we can set $c = 1/4$ and $n_0 = 64$ to obtain that
$(n\lg n)/2 - (3n)/2 \ge c n \lg n$ for all $n \ge n_0$.  Therefore, the
worst-case running time of {\sc Build-Heap'} is $\Omega(n \lg n)$.
\end{enumerate}

{\bf 3.  Searching through two unsorted lists} (12 points)

Given two unsorted lists $S_1$ and $S_2$ of $n$ numbers each, and a
number $x$, describe an $O(n \lg n)$ algorithm for finding whether
there exists a pair of elements, one from $S_1$ and one from $S_2$,
that add up to $x$.  (For partial credit, give a $\Theta(n^2)$
algorithm for this problem.)

{\bf Answer:} We first give a simple $\Theta(n^2)$ time algorithm.  Next, we
present an $O(n \lg n)$ time algorithm based on sorting and then scanning
through the sorted lists.  Finally, we indicate that we can obtain another
$O(n \lg n)$ time algorithm using sorting and binary search.
\begin{enumerate}
\item
A simple $\Theta(n^2)$ time algorithm can be obtained by checking for each
pair of elements $a \in S_1$ and $b \in S_2$ to see whether $a + b = x$.
Since there are $n^2$ pairs, this takes $O(n^2)$ time in the worst-case.
Since we may have to go through all of the pairs to determine the final
result, the worst-case input will require $\Omega(n^2)$ time.  Thus, the
running time of the algorithm is $\Theta(n^2)$.

\item
We can provide a more efficient algorithm using sorting.  Here is an outline
of one such algorithm.  We first subtract each element in the first list $S_1$
from $x$ to obtain a new list $S_3$ of $n$ elements.  Our task now reduces to
determining whether there exist two elements in $S_3$ and $S_2$ that are
identical.  We can determine this by sorting each of the lists $S_2$ and $S_3$
and then scanning through the sorted lists for identical elements using a
procedure similar to the merge procedure of mergesort.

\begin{tabbing}
1. \= Compute the set $S_3 = \{x - s \; : s \in S_1\}$\\
2. \> Sort $S_2$ and $S_3$ separately, both in nonincreasing order\\
3. \> $i = j = 1$\\
4. \> \mywhile\ \=  $i \le n$ and $j \le n$\\
5. \> \> \myif\ $S_1[i] = S_2[j]$ then \ret\ \mytrue\ and exit\\
6. \> \> \myelse\ if $S_1[i] > S_2[j]$, then $j = j + 1$ \myelse\ $i = i +
1$\\
7. \> \ret\ \myfalse
\end{tabbing}

For the running time of the algorithm, we note that the calculation of list
$S_3$ in step $1$ takes $O(n)$ time.  The sorting of the two lists takes $O(n
\lg n)$ time using heapsort or mergesort.  Finally the scan through the two
lists (steps 4 through 6) takes $O(n)$ time.  Therefore, the total running
time of the algorithm is $O(n \lg n)$.

\item
We can devise another $O(n \lg n)$ time algorithm by combining sorting and
binary search.  We first sort both the lists $S_1$ and $S_2$ separately.
Next, for each element $a \in S_1$, we check whether the element $x - a$
belongs to $S_2$.  This step can be performed using binary search.  If there
does exist an $a \in S_1$ such that $x - a$ is in $S_2$, then we return
\mytrue; otherwise, we return \myfalse.

Sorting takes $O(n \lg n)$ time.  Each binary search takes $O(\lg n)$ time.
Since there are at most $n$ binary searches, the total running time is $O(n
\lg n)$.
\end{enumerate}

{\bf 4.} Exercise 6.3--3 (8 points)

{\bf Answer:} Let $X$ be the random number denoting the number of dice on
which the player's number appears.  Since the probability that the player's
number appears on any given dice is $1/6$, we have the following
probability distribution for $X$.
\[ \Pr[X = i] = {3 \choose i} \left(\frac{1}{6}\right)^i
\left(\frac{5}{6}\right)^{3 - i}.\]
If $X = 0$, the payoff is $-1$; if $X = 1$, the payoff is $1$; if $X = 2$, the
payoff is $2$, and if $X = 3$, the payoff is $3$.  Therefore the expected
payoff equals:
\[ - \left(\frac{5}{6}\right)^3 +
3\frac{1}{6}\left(\frac{5}{6}\right)^2 +
6\left(\frac{1}{6}\right)^2\frac{5}{6} + 
3\left(\frac{1}{6}\right)^3 = -\frac{17}{216}.\]

{\bf 5.  The effect of group size on the running time of the selection
algorithm} (5 + 5 = 10 points)

In the algorithm {\sc Select} described in Section~10.3 of the text,
the input elements are divided into groups of 5.  Will the algorithm
work in linear time if they are divided into groups of 3? How about
groups of 7?

{\bf Answer:} We first give a somewhat imprecise argument that suffices
for our purposes in this class.  Then, to illustrate how we would go about
giving a formal complete proof, we give a precise argument for the ``groups of
7'' case. 

{\bf Groups of 7:} If the input elements are divided into groups of $7$, then
we need to place new bounds on the size of low and high sides of the partition
that are obtained in step~4 of {\sc Select} on page~190 of the text.  As
before, at least half of the medians found in step~2 are greater than or equal
to the median-of-medians $x$.  Since there are $\approx n/7$ groups in our
case, we find that at least half of the $n/7$ groups contribute $4$ elements
or more that are greater than $x$.  Thus, the number of elements greater than
$x$ is at least $4n/14 = 2n/7$.  Similarly, the number of elements that are
less than $x$ is at least (approximately) $2n/7$.  It thus follows that the
each of the two sides of the partition is of size at most $\approx 5n/7$.  We
thus get the following recurrence
\[ T(n) \le T(n/7) + T(5n/7) + O(n).\]
We can use the iteration method or the recursion tree approach to obtain that
$T(n)$ in $O(n)$.  The contributions at each level of the recursion tree form
a geometric series with a ratio of $6/7$.  Since $6/7 < 1$, this series
converges, and we get $T(n) = O(n)$.

{\bf Groups of 3:} {\sc Select} is not linear in the worst-case, however, if
we divide the input elements into groups of $3$ instead.  We get a good
indication of that when we try to follow the same argument as we have done
above.  Since we can only claim that half of the $\lceil n/3 \rceil$ groups
contribute $2$ elements each, the best lower bound for any side of the
partition that we are able to show is at most $2((1/2) \cdot (n/3))$, which is
at most $n/3$.  Thus the best upper bound for any side of the partition is at
least $2n/3$.  In fact, we can ensure this by choosing the input
appropriately. Assume that $n$ is a multiple of $6$.  We can select the input
such that the number of groups with medians greater than the median-of-medians
$x$ is exactly $(1/2)(n/3) = n/6$.  This implies that the number of elements
greater than $x$ is exactly $2n/6 + 1 = n/3 + 1$.  Therefore, the number of
elements less than $x$ is exactly $2n/3 - 1$.  We set the input rank such that
it falls in the low side of the partition.  If we do this for every level of
the recursion, then this yields a recurrence of the form
\[
T(n) \ge T(n/3) + T(2n/3 - 1) + \Theta(n),
\]
which leads to $T(n) = \Omega(n \lg n)$.  You can see this if you unravel the
recursion tree obtained by the above recurrence and note that each of the
$\Omega(\log n)$ levels of the recursion tree sum to $\Omega(n)$.

{\bf Precise analysis for groups of 7:} If the input elements are divided into
groups of $7$, then we need to place new bounds on the size of low and high
sides of the partition that are obtained in step~4 of {\sc Select} on page~190
of the text.  As before, at least half of the medians found in step~2 are
greater than or equal to the median-of-medians $x$.  Since there are $\lceil
n/7 \rceil$ groups in our case, we find that at least half of the $\lceil n/7
\rceil$ groups contribute $4$ elements or more that are greater than $x$,
except for the one group that has fewer than $7$ elements if $7$ does not
divide $n$ exactly, and the one group containing $x$ itself.  Discounting
these two groups, it follows that the number of elements greater than $x$ is
at least
\[
4\left(\left \lceil \frac{1}{2} \left \lceil \frac{n}{7} \right\rceil \right \rceil
 - 2\right) \ge \frac{2n}{7} - 8.
\]
Similarly, the number of elements that are less than $x$ is at least $2n/7 -
8$.  It thus follows that the each of the two sides of the partition is of
size at most $n - 2n/7 + 8 = 5n/7 + 8$.  Before establishing our recurrence,
we obtain a lower bound on $n$ such that $5n/7 + 8 < n$.  We note that the
preceding inequality holds whenever $n > 19$.  We now have the following
recurrence, where $n_0$ is a sufficiently large constant ($\ge 19$) that is
chosen later:
\[
T(n) \le \left \{
\begin{array}{ll}
	\Theta(1) & \mbox{ if $n \le n_0$.}\\
	T(\lceil n/7 \rceil) + T(5n/7 + 8) + O(n) & \mbox{ if $n > n_0$.}
\end{array}
\right.
\]
We now show by substitution that $T(n) \le cn$ for some constant $c$.  For our
induction basis, we will select $c$ big enough that $T(n) \le cn$ for all $n
\le n_0$.  Assume as our induction hypothesis that $T(m) \le cm$ for all $m <
n$.  Substituting this inductive hypothesis into the right-hand side of the
recurrence yields
\begin{eqnarray*}
T(n) & \le & c\lceil n/7 \rceil + c(5n/7 + 8) + O(n)\\
& \le & cn/7 + c + 5cn/7 + 8c + O(n)\\
& = & 6cn/7 + 9c + O(n)\\
& = & cn - (cn/7 - 9c - O(n))\\
& \le & cn,
\end{eqnarray*}
since we can pick $c$ and $n_0$ large enough that $cn/7 \ge 9c + O(n)$ for all
$n \ge n_0$.  (Note that this is where $n_0$ is specified.)  The choice of $c$
will depend on the hidden constant in the $O(n)$ term.  Moreover, note that
$c$ must also satisfy the induction basis as mentioned above.  So we will pick
the larger of the two values needed.  In any case, we can always select a $c$
and $n_0$ appropriately and this completes the proof.  Therefore, {\sc Select}
is linear if we divide the input elements into groups of $7$.


\junk{
{\bf 6. Selection from two sorted lists} (10 bonus points)

Design and analyze an efficient algorithm to select the median from a
set of $m+n$ keys given in the form of two sorted lists, one of length
$m$ and the other of length $n$.  For convenience, you may assume that
the $m+n$ keys are all distinct.  ({\em Hint:}\/ A running time of
$O(\log(\min\{m,n\}))$ is achievable.)
}
\end{document}
