\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}{28 January 1999}{7}

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

\bigskip

{\bf 1. (8 points)} We have seen the following bound in class.
\[\sum_{1 \le i \le n} i^2 = \Theta(n^3).\]
Derive an asymptotically tight bound on the summation 
\[\sum_{1 \le i\le n} i^c,\]
where $c \ge 0$ is a given constant real number.

{\bf Answer:} We derive an upper and a lower bound using the same idea
used in class.  For the upper bound, we note that for $1 \le i \le n$,
$i^c \le n^c$.  Therefore, for any $n \ge 1$, we can simplify the
summation as follows.
\begin{eqnarray*}
\sum_{1 \le i \le n} i^c \le n \cdot n^c = n^{c+1}.
\end{eqnarray*}
We thus obtain that $\sum_{1 \le i\le n} i^c = O(n^{c+_1})$. 

For the lower bound, we note that for any $i \ge \lceil n/2 \rceil$,
$i^c \ge (\lceil n/2 \rceil)^c$.  Therefore, for any $n \ge 1$, we can
simplify the summation as follows.
\begin{eqnarray*}
\sum_{1 \le i \le n} i^c & = & \sum_{1 \le i \le \lfloor n/2 \rfloor} i^c + \sum_{\lceil n/2 \rceil \le i \le n} i^c\\  
& \ge & \sum_{\lceil n/2 \rceil \le i \le n} i^c\\
& \ge & \lfloor n/2 \rfloor (\lceil n/2 \rceil)^c\\
& \ge & \left(\frac{n}{2} - 1\right)\left(\frac{n}{2}\right)^c\\
& \ge & \frac{n^{c+1}}{2^{c+1}} - \frac{n^{c}}{2^c}.
\end{eqnarray*}
The last term $n^{c+1}/2^{c+1} - n^c/2^c$ is at least
$n^{c+1}/2^{c+2}$ for $n \ge 4$.  Therefore, the given summation is
at least $n^{c+1}/2^{c+2}$ for $n \ge 4$, thus implying that it is
$\Omega(n^{c+1})$.  

The upper and lower bounds together give us that the summation is
$\Theta(n^{c+1})$.

({\bf Remark:} I have used floors and ceilings for the sake of precision and
completeness only.  We could have dropped the floors and ceilings and made the
calculation much simpler.)

{\bf 2. (12 points)} Arrange the following functions in order from the
slowest growing function to the fastest growing function.  Briefly
justify your answer.  ({\em Hint:} It may help to plot the functions
and obtain an estimate of their relative growth rates.  It may also
help to express each function as a power of $2$ and then compare.)

\[ 
n^{\lg n} \hs (\lg n)^n \hs n^{100} \hs 2^{\sqrt{\lg n}}
\]

{\bf Answer:} The order from slowest growing to the fastest growing
function is: $2^{\sqrt{\lg n}}$, $n^{100}$, $n^{\lg n}$, and $(\lg
n)^n$.  We prove this using three steps: (i) $2^{\sqrt{\lg n}} =
O(n^{100})$, (ii) $n^{100} = O(n^{\lg n})$, and (iii) $n^{\lg n} =
(\lg n)^n$.
\begin{itemize}
\item[(i)] We use the connection between asymptotic notation and limits.
\begin{eqnarray*}
\lim_{n \rightarrow \infty} \frac{2^{\sqrt{\lg n}}}{n^{100}} & = & 
\lim_{n \rightarrow \infty} \frac{2^{\sqrt{\lg n}}}{2^{100 \lg n}}\\
& = & \lim_{n \rightarrow \infty} \frac{1}{2^{100 \lg n - \sqrt{\lg n}}}\\
& = & 0,
\end{eqnarray*}
since $100 \lg n - \sqrt{\lg n}$ goes to $\infty$ as $n$ goes to
$\infty$.  Therefore, $2^{\sqrt{\lg n}} = O(n^{100})$.

\item[(ii)] We use the connection between asymptotic notation and limits.
\begin{eqnarray*}
\lim_{n \rightarrow \infty} \frac{n^{100}}{n^{\lg n}} & = & 
\lim_{n \rightarrow \infty} \frac{1}{n^{\lg n - 100}}\\
& = & 0,
\end{eqnarray*}
since $\lg n - 100$ goes to $\infty$ as $n$ goes to $\infty$.  Therefore,
$n^{100} = O(n^{\lg n})$.

\item[(iii)]
We use the connection between asymptotic notation and limits.
\begin{eqnarray*}
\lim_{n \rightarrow \infty} \frac{n^{\lg n}}{(\lg n)^{n}} & = & 
\lim_{n \rightarrow \infty} \frac{2^{\lg^2 n}}{2^{n\lg \lg n}}\\
& = & \lim_{n \rightarrow \infty} \frac{1}{2^{n\lg \lg n - \lg^2 n}}\\
0,
\end{eqnarray*}
since $n\lg \lg n - \lg^2 n$ goes to $\infty$ as $n$ goes to $\infty$.
In fact, even $n - \lg^2 n$ goes to $\infty$ as $n$ goes to $\infty$.
Therefore, $n^{\lg n} = O((\lg n)^{n})$.
\end{itemize}

{\bf 3. (3 $\times$ 6 = 18 points)} Let $f(n)$, $g(n)$, and $h(n)$ be
asymptotically positive and monotonically increasing functions.  Prove
or disprove each of the following conjectures.
\begin{itemize}
\item[{\bf (a)}]
$f(n) + g(n) = \Theta(\min\{f(n), g(n)\})$.

{\bf Answer:} This statement is false.  Let $f(n) = 1$ and $g(n) = n$.
Then $f(n) + g(n) = n + 1$, while the function $\min\{f(n), g(n)\} =
1$ for all $n$.  Clearly, $n + 1 \neq \Theta(1)$. 

While the claim $n + 1 \neq \Theta(1)$ is obvious, if we are asked to
prove formally, we can prove it as follows.  It suffices to show that
$n + 1 \neq O(1)$.  Indeed, if $n + 1 = O(1)$, then there exist
positive constants $c$ and $n_0$ such that $n + 1 \le c$ for all $n
\ge n_0$.  This implies that $n \le c - 1$ for all $n \ge n_0$, an
obvious contradiction.

\item[{\bf (b)}]
If $f(n) = O(h(n))$ and $g(n) = \Omega(h(n))$, then $f(n) = O(g(n))$.

{\bf Answer:} This statement is true.  We are given that $f(n) =
O(h(n))$, which implies that there exist positive constants $c_0$ and
$n_0$ such that $f(n) \le c_0 h(n)$ for all $n \ge n_0$.  We are also
given that $g(n) = \Omega(h(n))$, which implies that there exist
positive constants $c_1$ and $n_1$ such that $g(n) \ge c_1 h(n)$ for
all $n \ge n_1$.  Putting these two statements together, we obtain
that for all $n \ge \max\{n_0, n_1\}$, we have the following
inequality:
\[
f(n) \le c_0 h(n) \le c_0 \frac{g(n)}{c_1} = \frac{c_0}{c_1} g(n).
\]
If we set $n_2 = \max\{n_0, n_1\}$ and $c_2 = c_0/c_1$, we obtain that
$f(n) \le c_2 g(n)$ for all $n \ge n_2$.  Therefore, $f(n) = O(g(n))$.

\item[{\bf (c)}]
$f(n^2) = \Omega((f(n))^2)$.

{\bf Answer:} This statement is false.  Let $f(n) = \lg n$.  We then
have $f(n^2) = \lg(n^2) = 2\lg n$.  On the other hand, $(f(n))^2 =
(\lg n)^2$.  We now show that $\lg n + 1 \neq \Omega((\lg n)^2)$.
Indeed, if we assume the contrary, then there exist positive constants
$c$ and $n_0$ such that $2\lg n \ge c (\lg n)^2$ for all $n \ge n_0$.
This implies that $\lg n \le c/2$ for all $n \ge n_0$, an obvious
contradiction.
\end{itemize}

{\bf 4. (3 $\times$ 6 = 18 points)} Solve the following recurrences.
Assume that $T(n)$ is constant for $n \ge 3$.  Make your bounds as
tight as possible, and justify your answers.
\begin{itemize}
\item[{\bf (a)}] 
$T(n) = T(n - 1) + \lg n$.

{\bf Answer:} We use the iteration method.
\begin{eqnarray*}
T(n) & = & \lg n + \lg(n - 1) + T(n-2)\\
& = & \lg n + \lg (n-1) + \lg (n-2) + T(n-3)\\
& = & T(1) + \sum_{2 \le i \le n} \lg i.
\end{eqnarray*}
We now derive upper and lower bounds.  For $2 \le i \le n$, we have
$\lg i \le \lg n$.  Therefore, we obtain $T(n) \le T(1) + (n-1)\lg n
\le \Theta(1) + n \lg n = O(n \lg n)$.

For the lower bound, we note (as in Problem~1 above) that for $n/2 < i
\le n$, $\lg i \ge \lg(n/2)$.  Therefore, we obtain that $T(n) \ge
T(1) + (n/2) \lg(n/2) = \Theta(1) + (n\lg n)/2 - n/2 = \Omega(n \lg n)$.

We thus obtain that $T(n) = \Theta(n \lg n)$.

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

{\bf Answer:} We again use the iteration method, this time using the
recursion tree.  The contribution of the first level of the recursion
tree is $2n$.  The contribution of the second level is $2n/5 + 2n/3 =
(2n)(8/15)$.  The contribution of the third level is $2n/5^2 + 2n/15 +
2n/15 + 2n/3^2 = (2n)(64/225) = 2n(8^2/15^2)$.  We thus obtain the
following summation.
\begin{eqnarray*}
T(n) & \le & \sum_{i \ge 0} 2n\left(\frac{8}{15}\right)^i\\
& = & \frac{2n}{1 - 8/15}\\
& = & \frac{30 n}{7}.
\end{eqnarray*}
Therefore, $T(n) = O(n)$.  For a lower bound, we simply note that
$T(n) \ge n$, thus implying that $T(n) = \Omega(n)$.  We thus have
$T(n) = \Theta(n)$.

\item[{\bf (c)}]
$T(n) = 10T(n/3) + n^2$.

{\bf Answer:} We use the Master Theorem.  We have $a = 10$, $b= 3$,
and $f(n) = n^2$.  Therefore, $n^{\log_b a} = n^{\log_3 10} =
n^{2.1}$.  This falls under Case~1 since we see that for $\eps = .1$,
$n^2 = O(n^{2.1}/n^\eps)$.  Thus, we obtain that $T(n) =
\Theta(n^{\log_b a}) = \Theta(n^{\log_3 10})$.
\end{itemize}

{\bf 5. (2 $\times$ 7 = 14 points)}  Parts~(a) and~(b) of Problem~5--2.
\begin{itemize}
\item[(a)] In any group of $n \ge 2$ people, there are two people with the
same number of friends in each group.

{\bf Answer:} In graph-theoretic terminology, the statement can be written as:
In any undirected graph $G$ with $n \ge 2$ vertices, there exist two vertices
that have the same degree.

We now prove the above statement.  We first prove the statement under the
assumption that no vertex in $G$ has degree $0$.  The graph $G$ has $n$
vertices, each of which has degree at least $1$ and at most $n - 1$.  Since
there are only $n - 1$ distinct integers between $1$ and $n - 1$, it follows
that there must be two vertices with the same degree.  ( Another way to see
the argument is that we cannot have $n$ {\em distinct\/} degrees among $n - 1$
distinct values.)

So far we have assumed that there is no vertex in $G$ with degree $0$.  We now
deal with the case where there are degree-$0$ vertices.  If there are more
than one, then the desried claim trivially holds.  If there is exactly one,
then we can remove from $G$ and obtain a new undirected graph $G'$ that has at
least two vertices and in which every vertex has degree at least $1$.  We can
prove the desired claim by invoking the proof of the previous paragraph on $G'$.

\item[(b)] Every group of six people contains either three mutual friends or
three mutual strangers.

{\bf Answer:} In graph-theoretic terminology, the statement can be written as:
In any undirected graph $G = (V, E)$ with six vertices, there exist three
vertices $u$ ,$v$, and $w$ in $V$ such that either $(u,v)$, $(v,w)$, and $(u,w)$
all belong to $E$ or none of $(u,v)$, $(v,w)$, and $(u,w)$ belongs to $E$.

Let us number the six vertices of the graph $1$ through $6$.  In the following
proof, we will use the ``friends'' terminology rather than the graph-theoretic
terminology.  Consider vertex $1$.  We consider two cases depending on the
number of friends of $1$.

The first case is in which the number of friends of $1$ is at least three.
Without loss of generality, let the three friends of $1$ be $2$, $3$, and $4$.
If any two of $2$, $3$, and $4$ are friends of each other, say $2$ and $3$,
then we have found three persons ($1$, $2$, and $3$) who are mutual friends
and we are done.  Otherwise, none of $2$, $3$, and $4$ are friends, and hence
they are mutual strangers, and we are again done.

The second case is in which the number of friends of $1$ is less than three.
In this case, there are three persons, say $2$, $3$, and $4$, who are not
friends of $1$.  If $2$, $3$, and $4$ are all mutual friends, then we are
done.  Otherwise, there exist two persons among $2$, $3$, and $4$, say $2$ and
$3$ who are not friends.  In this case, $1$, $2$, and $3$ are mutual
strangers.  This completes the proof of the desired claim.
\end{itemize}
\end{document}
