\documentclass[11pt]{article}
\usepackage{program}


\title{6.046 Problem Set 2}
\author{Chris Laas: Section G}
\date{February 15, 2000}

\pagestyle{myheadings}
\markright{Chris Laas: Section G \hfil 6.046J/18.410J \hfil 2/15/2000}

\renewcommand{\labelenumi}{(\alph{enumi})}
\renewcommand{\labelenumii}{\arabic{enumii}}
\NumberProgramstrue
\def\RETURN{\keyword{return}\ }
\def\MOD{\mbox{mod}\ }
\def\text#1{\mbox{ #1 }}

\begin{document}
\maketitle

\section*{Problem 2-1}

\begin{enumerate}
\item%(a)
Since $\log_5 6 \approx 1.113$ and $n \lg^6 n = O(n^{1.113 - \epsilon})$
for $\epsilon \approx 0.1$, $T(n) = \Theta(n^{\log_5 6})$ by the
Master Theorem.

\item%(b)
Since $\log_6 5 \approx 0.898$ and $n = \Omega(n^{0.898 + \epsilon})$
for $\epsilon \approx 0.1$, and $\frac{5 n}{6} \leq c n$ for $c = 5/6$
and all $n \geq 0$, $T(n) = \Theta(n)$ by the Master Theorem.

\item%(c)
Since $\log_9 3 = 1/2$ and $\sqrt{n} = n^{1/2} = \Theta(n^{1/2})$,
$T(n) = \Theta(\sqrt{n} \lg n)$ by the Master Theorem.

\item%(d)
Let $m = \lg n$.  Then $T(2^m) = 4T(2^{m/2}) + m^2$.  Letting
$S(m) = T(2^m)$, we have $S(m) = 4S(m/2) + m^2$.  Since $\log_2 4 = 2$
and $m^2 = \Theta(m^2)$, we have $S(m) = \Theta(m^2 \lg m)$ by the
Master Theorem.  Thus $T(n) = T(2^m) = S(m) = \Theta(m^2 \lg m)
 = \Theta(\lg^2 n \lg \lg n)$.

\item%(e)
$T(n) = \sum_{k=1}^{n} k^2 + \Theta(1)$.  To show this, we prove by
induction that $T(n) = \sum_{k=1}^{n} k^2 + c$ for some constant $c$:
\begin{eqnarray*}
T(n) & = & \sum_{k=1}^{n} k^2 + c \\
     & = & \sum_{k=1}^{n-1} k^2 + n^2 + c \\
     & = & T(n-1) + n^2
\end{eqnarray*}

Thus:
\begin{eqnarray*}
T(n) & = & \sum_{k=1}^{n} k^2 + \Theta(1) \\
     & = & \frac{n(n+1)(2n+1)}{6} + \Theta(1) \\
     & = & \Theta(n^3)
\end{eqnarray*}

\item%(f)
$T(n) = \Theta(2^n)$.

First, we will show that $T(n) = O(2^n)$.  Assume that
$T(n-1) \leq c 2^{n-1} - b$.  Then:
\begin{eqnarray*}
T(n) & \leq & 2 (c 2^{n-1} - b) + 1 \\
     & =    & c 2^n - 2 b + 1 \\
     & \leq & c 2^n - b
\end{eqnarray*}
for any $b > 0$.  For the base case $T(1) = 1$,
$T(1) = 1 \leq c 2^1 - b = 2c - b$ for any $c > \frac{b + 1}{2}$.

Now, to show that $T(n) = \Omega(2^n)$, assume that
$T(n-1) \geq c 2^{n-1}$.  Then:
\begin{eqnarray*}
T(n) & \geq & 2 c 2^{n-1} + 1 \\
     & =    & c 2^n + 1 \\
     & \geq & c 2^n
\end{eqnarray*}
For the base case $T(1) = 1$,
$T(1) = 1 \geq c 2^1 = 2c$ for any $c < \frac{1}{2}$.

Thus, since $T(n) = O(2^n)$ and $T(n) = \Omega(2^n)$, $T(n) = \Theta(2^n)$.

\item%(g)
$T(n) = \Theta(n \lg n)$

\item%(h)
$T(n) = \Theta(n)$.

First, we will show that $T(n) = O(n)$.  Assume that
$T(\frac{n}{3} + 1) \leq c (\frac{n}{3} + 1)$.  Then:
\begin{eqnarray*}
T(n) & \leq & 2 c (\frac{n}{3} + 1) + n \\
     & =    & \frac{2cn}{3} + 2c + n \\
     & =    & \frac{2c + 3}{3} n + 2c \\
     & \leq & c n
\end{eqnarray*}
for $c > 3$ and $n > 24$.  For the base case $T(25) = 1$,
$T(25) = 1 \leq c 1 = c$.

Now, to show that $T(n) = \Omega(n)$, assume that
$T(\frac{n}{3} + 1) \geq c (\frac{n}{3} + 1)$.  Then:
\begin{eqnarray*}
T(n) & \geq & 2 c (\frac{n}{3} + 1) + n \\
     & =    & \frac{2cn}{3} + 2c + n \\
     & =    & \frac{2c + 3}{3} n + 2c \\
     & \geq & c n
\end{eqnarray*}
for $c < 3$.  For the base case $T(25) = 1$,
$T(25) = 1 \geq c 1 = c$ for $c < 1$.

\item%(i)
$T(n) = \Theta(n \lg n)$.

\item%(j)
$T(n) = \Theta(\frac{n}{\lg n})$.


\end{enumerate}

\newpage


\section*{Problem 2-2}

\begin{enumerate}
\item%(a)
The proper recurrence relation is:
$$ T(n) = T\left(\frac{n}{p+1}\right) + 1 $$

The base case is $T(1) = 1$.

The exact solution is $T(n) = \log_{p+1} n + 1$.  The base case holds:
$$ T(1) = \log_{p+1} 1 + 1 = 0 + 1 = 1 $$

And the inductive case holds:
\begin{eqnarray*}
T\left(\frac{n}{p+1}\right) + 1
           & = & \left(\log_{p+1}\left(\frac{n}{p+1}\right) + 1\right) + 1 \\
           & = & (\log_{p+1} n - \log_{p+1}(p+1) + 1) + 1 \\
           & = & (\log_{p+1} n - 1 + 1) + 1 \\
           & = & \log_{p+1} n + 1 \\
           & = & T(n)
\end{eqnarray*}

\item%(b)

No: for constant $p$,
$T(n) = \log_{p+1} n + 1 = \frac{\lg n}{\lg (p+1)} + 1 = \Theta(\lg n)$,
which is the same order of growth as the original binary search.

\end{enumerate}

\newpage


\section*{Problem 2-3}

\begin{enumerate}
\item
% (a)

I assume we're getting an array $A$ of tasks.  First, the array is
sorted (in $n \lg n$ time) in nondecreasing order by
$|Start-Time|$.  Then, each pair of subsequent (by $|Start-Time|$)
tasks is compared to see whether they overlap, and if so, the
algorithm returns {\bf true}.

\begin{program}
|Any-Overlapping-Tasks?|(A)
\quad\tab |Quicksort|_{\mbox{\scriptsize{}|Start-Time|}}(A, 1, |Length|(A)) \label{qsort}
          \FOR i \gets 2 \rdots |Length|(A)
              \IF |Start-Time|(A[i]) < |End-Time|(A[i-1])
                 \THEN \RETURN \true
                 \untab%
              \untab%
          \untab%
          \RETURN \false
\end{program}

In the sorted $A$, if there is any $i \in \{ 2,\dots,n \}$ such that
$|Start-Time|(A[i]) < |End-Time|(A[i-1])$, then clearly tasks $i-1$
and $i$ overlap.  Conversely, if any two tasks $A[i]$ and $A[j]$
(with $i < j$) overlap, then $|Start-Time|(A[j]) < |End-Time|(A[i])$.
Thus $A[i]$ and $A[i+1]$ must overlap, since
$|Start-Time|(A[i+1]) \leq |Start-Time|(A[j]) < |End-Time|(A[i])$.
Thus the algorithm will return true if and only if any two tasks in
$A$ overlap.  Since $|Quicksort|$ is known to terminate, and the {\bf
for} loop is guaranteed not to perform more than $n-1$ iterations, the
algorithm must terminate.

Since line~\ref{qsort} takes $\Theta(n \lg n)$ steps to perform, and
the rest of the algorithm only takes $\Theta(n)$ steps, the whole
algorithm runs in $\Theta(n \lg n)$ time.


\item
% (b)

First, we must define a binary search which will locate the interval
of subsequent start times in which a particular end time resides.
More specifically, given a sorted (nondecreasing by $|Start-Time|$)
array $A$, integers $a$ and $b$ such that $1 \leq a < b \leq n$, and a
time $v$ such that $|Start-Time|(A[a]) < v < |Start-Time|(A[b])$, the
algorithm returns an integer $c$ such that
$|Start-Time|(A[c]) < v < |Start-Time|(A[c+1])$.

\begin{program}
|Binary-Search-Start-Time|(A, a, b, v)
\quad\tab \IF b - a = 1
             \THEN \RETURN a
             \untab%
          \untab%
          k \gets \lfloor\frac{a+b}{2}\rfloor
          \IF v < |Start-Time|(A[k])
             \THEN \RETURN |Binary-Search-Start-Time|(A, a, k, v)
             \ELSE \RETURN |Binary-Search-Start-Time|(A, k, b, v)
\end{program}

Since $b - a$ is monotonically decreasing with each recursion (and the
algorithm stops when it reaches 1), the algorithm is guaranteed to
terminate.  Since the precondition on the recursive invocation is
always guaranteed by the {\bf if} condition, and the precondition plus
the termination condition guarantees the postcondition, the algorithm
is correct.

Like all binary searches, this runs in $\Theta(\lg n)$ time, since the
recurrence relation of the run time is $T(n) = T(n/2) + \Theta(1)$.

Now we can define the primary algorithm.  Like the algorithm for part
(a), it begins by sorting $A$ (in $n \lg n$ time) in nondecreasing
order by $|Start-Time|$, and initializing the count of overlapping
pairs to zero.  Then, for each task $A[i]$, the algorithm determines
the number of other tasks which overlap it.  In the special case that
the end time of $A[i]$ is after the last task's start time, that
number ($x$) is $n - i$.  In all other cases, the specialized binary
search developed above is used to determine the index of the last task
which overlaps $A[i]$, and $i$ is subtracted to give the number of
overlapping tasks.  This number $x$ is added to the running count of
overlapping pairs, which, after all tasks have been processed, is
the return value of the algorithm.

\begin{program}
|Count-Overlapping-Tasks|(A)
\quad\tab |Quicksort|_{\mbox{\scriptsize{}|Start-Time|}}(A, 1, |Length|(A)) \label{qsort2}
          |count| \gets 0
          \FOR i \gets 1 \rdots |Length|(A)
              \IF |Start-Time|(A[|Length|(A)]) < |End-Time|(A[i])
                 \THEN x \gets |Length|(A) - i
                 \ELSE x \gets |Binary-Search-Start-Time|(A, i, |Length|(A), |End-Time|(A[i])) - i
                 \untab%
              \untab%
              |count| \gets |count| + x
          \untab%
          \RETURN |count|
\end{program}

$|Quicksort|$ and $|Binary-Search-Start-Time|$ are already known to
terminate; since the number of iterations of the {\bf for} loop must
be $n$, this algorithm must terminate.  Since $|count|$ is a simple
accumulator, the result of the algorithm is
$\sum_{i=1}^n |overlaps|(A[i])$, where $|overlaps|(A[i])$ is the value
of $x$ on the $i$th iteration through the loop.  In the case in which
$|Start-Time|(A[|Length|(A)]) < |End-Time|(A[i])$, then $A[i]$ clearly
overlaps every task which starts after it, so
$|overlaps|(A[i]) = |Length|(A) - i$.  In the other case, we use
$|Binary-Search-Start-Time|$ to find the integer $c$ such that
$$|Start-Time|(A[c]) < |End-Time|(A[i]) < |Start-Time|(A[c+1])$$
Since all tasks $A[j]$ such that $j \in \{ i+1,\dots,c \}$ overlap task
$A[i]$, $|overlaps|(A[i]) = c - i$.  Thus, the algorithm correctly
counts the number of pairs of overlapping tasks.

Line~\ref{qsort} takes $\Theta(n \lg n)$ steps to perform.  The loop
body is executed $n$ times, and each iteration takes $\Theta(\lg n)$
steps (in the worst case); thus the loop takes $\Theta(n \lg n)$
steps.  Thus, the algorithm runs in $\Theta(n \lg n)$ time.


\end{enumerate}

\newpage


\section*{Problem 2-4}
\begin{enumerate}
\item%(a)
$T(n) = \Theta(n^2)$

\item%(b)
The algorithm would divide $A(x)$ into $A_1(x)$ and $A_2(x)$, and
$B(x)$ into $B_1(x)$ and $B_2(x)$.  Then it would recurse to calculate
$A_1(x) B_1(x)$, $A_1(x) B_2(x)$, $A_2(x) B_1(x)$, and $A_2(x) B_2(x)$,
and then adds them together, shifted properly to take into account the
factors of $x^\frac{n}{2}$ and $x^n$.  This takes $2n$ additions.
Thus, the recurrence relation is:
$$ T(n) = 4 T\left(\frac{n}{2}\right) + 2 n $$

Since the time to multiply two degree 0 polynomials (i.e., constants)
is defined to be 1, the base case is $T(1) = 1$.

The exact solution of this recurrence is $T(n) = 3 n^2 - 2 n$.  First,
I show it matches the base case: $T(1) = 3 - 2 = 1$.  Next, I show it
solves the recurrence relation:
\begin{eqnarray*}
4 T\left(\frac{n}{2}\right) + 2 n
& = & 4 \left(3 \left(\frac{n}{2}\right)^2 - 2 \left(\frac{n}{2}\right)\right) + 2 n \\
& = & 3 n^2 - 4 n + 2 n \\
& = & 3 n^2 - 2 n \\
& = & T(n)
\end{eqnarray*}

This completes the proof.

\item%(c)
Instead of calculating $A_1(x) B_1(x)$, $A_1(x) B_2(x)$,
$A_2(x) B_1(x)$, and $A_2(x) B_2(x)$ separately, the improved
algorithm computes $P_1(x) = A_1(x) B_1(x)$, $P_2(x) = A_2(x) B_2(x)$, and
$ P_3(x) = (A_1(x) + A_2(x))(B_1(x) + B_2(x)) $ by recursing.  It then
calculates
$$ C(x) = P_1(x) + x^{\frac{n}{2}}(P_3(x) - P_1(x) - P_2(x)) + x^n P_2(x) $$
Calculating $P_3(x)$ takes $n$ additions, and calculating $C(x)$ given
$P_1(x)$, $P_2(x)$, and $P_3(x)$ takes $3n$ additions.  Thus, the
recurrence relation is:
$$ T(n) = 3 T\left(\frac{n}{2}\right) + 4 n $$
The base case is again $T(1) = 1$.

Since $\log_2 3 \approx 1.585$ and $4 n = O(n^{1.585 - \epsilon})$ for
$\epsilon \approx 0.5$, $T(n) = \Theta(n^{\lg 3})$, by the Master Theorem.

\end{enumerate}
\newpage


\section*{Problem 2-5}

$$ T(m, n) = \left\{ \begin{array}{ll}
m + n - 1 & \text{if} n > 0 \text{and} m > 0 \\
0         & \text{else}
\end{array} \right.
$$

Proof: if $n = 0$ or $m = 0$, the solution is correct by definition.
If $n = 1$ and $m = 1$,
$T(min(m,n), max(m,n)-1) + 1 = T(1,0) + 1 = 0 + 1 = 1 = 1 + 1 - 1 =
T(m,n)$, so the solution is correct for $m=n=1$.
Else, $min(m,n) > 0$ and $max(m,n)-1 > 0$, so
\begin{eqnarray*}
T(min(m,n), max(m,n)-1) + 1 & = & (min(m,n) + (max(m,n)-1) - 1) + 1 \\
                            & = & (min(m,n) + max(m,n)) - 1 - 1 + 1 \\
                            & = & (m + n) - 1 \\
                            & = & T(m,n) \\
\end{eqnarray*}

Thus the solution holds for all cases.

\newpage


\section*{Problem 2-6}
\begin{enumerate}

\item%(a)
Since each iteration of the loop body takes $\Theta(n^2)$ time and the
loop is executed at most $e_{|max|} = 2^n - 1$ times, the worst-case
running time of the algorithm is $\Theta(n^2 2^n)$

\item%(b)

This algorithm follows directly from the inductive definition of
$x^e \ (\MOD N)$.  For the base case, if $e = 1$, then the result is
$x$.  Else, if $e$ is even, the value of $x^{e/2} \ (\MOD N)$ is
computed by recursing, and is squared to give the result.  If $e$ if
odd, then the value of $x^{(e-1)/2} \ (\MOD N)$ is computed by
recursing, is squared, and is then multiplied by $x$ to give the
result.

\begin{program}
|Repeated-Square-Exponentiate|(x, e, N)
\quad\tab \IF e = 1
             \THEN \RETURN x
             \untab%
          \untab%
          \IF e = 0 \ (\MOD 2)
             \THEN y \gets |Repeated-Square-Exponentiate|(x, e/2, N)
                   \RETURN y \times y \ (\MOD N)
             \ELSE y \gets |Repeated-Square-Exponentiate|(x, (e-1)/2, N)
                   \RETURN (y \times y \ (\MOD N)) \times x \ (\MOD N)
             \untab%
          \untab%
\end{program}

The algorithm is guaranteed to give the correct result, as it follows
the definition of the exponential to the letter.  It will always
terminate because $e$ decreases monotonically with each recursion, and
the recursion terminates when $e = 1$.

The number of multiplications executed by the algorithm is given by
the recurrence relation
$$ T_{\times}(e) = T_{\times}(\lfloor\frac{e}{2}\rfloor) + \left\{ \begin{array}{ll}
1 & \text{if $e$ is even} \\
2 & \text{if $e$ is odd} \\
\end{array} \right.
$$
More concisely, $T_{\times}(e) = T_{\times}(\lfloor\frac{e}{2}\rfloor) + \Theta(1)$.
Thus,
$$T_{\times}(e) = \Theta(\lg e) = \Theta(n)$$

The number of Mod operations executed by the algorithm is given by
the recurrence relation
$$ T_{|mod|}(e) = T_{|mod|}(\lfloor\frac{e}{2}\rfloor) + \left\{ \begin{array}{ll}
1 & \text{if $e$ is even} \\
2 & \text{if $e$ is odd} \\
\end{array} \right.
$$
Add 1 to this if you count the ``mod 2'', which in a practical
implementation would take effectively zero time.
Concisely, $T_{|mod|}(e) = T_{|mod|}(\lfloor\frac{e}{2}\rfloor) + \Theta(1)$.
Thus, as for multiplication,
$$T_{|mod|}(e) = \Theta(\lg e) = \Theta(n)$$

\item%(c)

Since there are $\Theta(n)$ multiplications plus modulo operations run
by the algorithm, and each operation takes $\Theta(n^2)$ time, the
algorithm runs in $\Theta(n^3)$ time.

\end{enumerate}
\newpage


\end{document}
