\documentclass[11pt]{article}

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

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

\begin{document}
\maketitle

\section*{Problem 1-1}

\begin{tabular}{l|llllll}
    & $O$ & $o$ & $\Omega$ & $\omega$ & $\Theta$ \\
\hline
(a) & no & no & yes & no & no \\
(b) & no & no & yes & yes & no \\
(c) & no & no & yes & yes & no \\
%(d) & yes & yes & no & no & no \\
%(d) & yes & no & no & no & no \\
(d) & yes & no & yes & no & yes \\
(e) & no & no & yes & yes & no \\
(f) & no & no & no & no & no & (uncomparable) \\
(g) & yes & no & yes & no & yes \\
(h) & yes & no & yes & no & yes \\
(i) & yes & no & no & no & no \\
\end{tabular}

\newpage

\section*{Problem 1-2}

\renewcommand{\labelenumi}{(\alph{enumi})}
\renewcommand{\labelenumii}{\arabic{enumii}}
\begin{enumerate}

% (a)
\item
 \begin{enumerate}
 \item No: consider $f(n) = n$ and $g(n) = n \lg n$ from
 the example solution.
 \item No: again consider the same functions and the scenario in the
 example.
 \item Yes.  Since $g(n) = \Omega(f(n) \lg n)$, there exists some
 constants $c > 0$ and $n_0 > 0$ such that $g(n) \geq c f(n) \lg n$
 for all $n \geq n_0$.  Choosing $n_0 > 2^{1/c}$ ensures that
 $c \lg n > 1$ for all $n > n_0$, and thus $g(n) > f(n)$ for all
 $n > n_0$.
 \item No, since as we saw above, $g(n) > f(n)$ for all $n > n_0$ for
 some constant $n_0 > 0$.
 \end{enumerate}

%(b)
\item
 \begin{enumerate}
 \item No: consider again the example from the example solution.
 \item No: as above.
 \item Yes.  Since $g(n) = \Theta(f(n) \lg n)$, we also have that
 $g(n) = \Omega(f(n) \lg n)$.  Thus, as in section (a), A is faster
 than B for all n greater than some $n_0$.
 \item No, since as we saw above, $g(n) > f(n)$ for all $n > n_0$ for
 some constant $n_0 > 0$.
 \end{enumerate}

%(c)
\item
 \begin{enumerate}
 \item No: consider again the example from the example solution.
 \item No: as above.
 \item No.  Consider $f(n) = 2$ and $g(n) = 1$.  Clearly $f(n) > g(n)$
 for all $n$.
 \item No.  Consider again $f(n) = n$ and $g(n) = n \lg n$ from the
 example solution.  As we saw before, for all $n > 2$, $g(n) > f(n)$.
 \end{enumerate}

%(d)
\item
 \begin{enumerate}
 \item No.  Consider $f(n) = n$ and $g(n) = 1$.  Clearly
 $f(n) > g(n)$ for all $n > 1$.
 \item No.  Consider $f(n) = 1$ and $g(n) = \sqrt{\lg n}$.  Clearly
 $f(n) < g(n)$ for all $n > 2$.
 \item No.  Consider again the example $f(n) = n$ and $g(n) = 1$ from above.
 \item No.  Consider again the example $f(n) = 1$ and
 $g(n) = \sqrt{\lg n}$ from above.
 \end{enumerate}

\end{enumerate}

\newpage

\section*{Problem 1-3}

The ``for'' loop form of the algorithm seems a little unclear to me;
for clarity, I specify that the indices of $a$ range from 0 to
$length[a] - 1$, that $i$ is initialized to $length[a] - 1$, that the
loop as written is iterated once through for each of the values of $i$
in $\{ length[i]-1, \dots, 0 \}$, and that at the loop termination,
$i = -1$.

The loop invariant of this algorithm is, for $k = length[a]$,
$$ value = a_{i+1} + a_{i+2} x + a_{i+3} x^2 + \dots + a_{k-1} x^{k-i-2} $$
or, more concisely,
$$ value = \sum_{j=i+1}^{k-1} a_j x^{j-i-1} $$
This condition holds true at the beginning of each iteration (between
lines 2 and 3).

At the beginning of the first iteration, $value$ is initialized to 0,
and $i$ is initialized to $length[a] - 1 = k - 1$.  Since
$$ 0 = \sum_{j=k}^{k-1} a_j x^{j-i-1} $$
the loop invariant is seen to hold in the base case.

Now, the inductive hypothesis gives us that
$$ value = \sum_{j=i+1}^{k-1} a_j x^{j-i-1} $$
at the beginning of a given iteration.  Let $value'$ and $i'$ be the
values of $value$ and $i$ at the beginning of the next iteration.  We
must show that
$$ value' = \sum_{j=i'+1}^{k-1} a_j x^{j-i'-1} $$
Since $value' = a_i + value * x$ and $i' = i - 1$, we have:
\begin{eqnarray*}
value' & = & a_i + x \sum_{j=i+1}^{k-1} a_j x^{j-i-1} \\
       & = & a_i + \sum_{j=i+1}^{k-1} a_j x^{j-i} \\
       & = & a_{i'+1} + \sum_{j=i'+2}^{k-1} a_j x^{j-i'-1} \\
       & = & \sum_{j=i'+1}^{k-1} a_j x^{j-i'-1} \\
\end{eqnarray*}

Thus the condition holds at the beginning of the next iteration.

Now, since we have proven the loop invariant, after the last iteration
of the ``for'' loop, the following condition holds:
$$ value = \sum_{j=i+1}^{k-1} a_j x^{j-i-1} \mbox{\bf and } i = -1 $$
This implies that
$$ value = \sum_{j=0}^{k-1} a_j x^{j} $$
and, as this is the desired postcondition, we have shown that when the
loop terminates, $value$ holds the correct evaluation of the
polynomial.

Lastly, it is easy to prove that this loop terminates: $i$ begins as
$$ length[a] - 1 \geq -1 $$
initially, decreases by one at every
iteration, and when it reaches -1 the loop must terminate.  Thus, the
loop must terminate after a finite number of steps on every invokation.

\newpage

\section*{Problem 1-4}

\begin{enumerate}
\item
Since insertion sort takes $\Theta(n)$ steps and mergesort takes
$\Theta(n \lg n)$ steps on an input sequence already sorted in
nondecreasing order, the insertion sort is faster.

Since insertion sort takes $\Theta(n^2)$ steps and mergesort takes
$\Theta(n \lg n)$ steps on an input sequence already sorted in
nonincreasing order, the mergesort is faster.

And, since insertion sort takes $\Theta(n^2)$ steps and mergesort
takes $\Theta(n \lg n)$ steps on a random input sequence, the
mergesort is faster.

\item
Insertion sort, as defined in chapter one of the book, is certainly
stable, since a datum will never be moved past another datum of equal
value.

Whether mergesort is stable depends entirely on the definition of the
Merge function.  If the Merge function is implemented in the
straightforward manner, preserving the internal order of the two
subarrays and placing data from the first subarray before equal-valued
data from the second subarray in the merged array, then mergesort is
stable.

\item
See above; if implemented in the manner described, both insertion sort
and merge sort are stable.

\end{enumerate}

\newpage

\section*{Problem 1-5}

To add two numbers $a$ and $b$ to produce a result $c$, first start
with $c = 0$.  Take the lowest digits of $a$ and $b$ and add them
together, putting the result's lowest digit in the lowest digit of
$c$, and remembering the carry value (if any).  Then take the next
lowest digits of $a$ and $b$ and add them together, and add the
previous carry value to that.  Take the lowest digit of the result and
put it in the second-to-lowest digit of $c$, and remember the second
digit of the result as the carry value (if any).  Repeat this
procedure until there are no more digits left in $a$ and $b$.  (The
high-order digits of the smaller of $a$ or $b$ should be padded out
with zeros to the same length as the larger, of course.)  The highest
digit of $c$ should be the final carry digit.

To multiply two numbers $a$ and $b$ to produce a result $c$, first
start with $c = 0$.  Take the lowest digit of $b$, multiply it by $a$,
and add the result to $c$.  (Of course, if the numbers are in binary,
this means that you should add $a$ to $c$ if and only if the lowest
digit of $b$ is 1.  If they aren't in binary, you use your trusty
multiplication tables.)  Take the next lowest digit of $b$, multiply
it by $a$, and add the result, shifted over by one digit, to $c$.
Repeat the process for each digit of $b$, shifting over by one more
digit each time, until there are no more digits left in $b$.

Implemented as a ripple carry adder, my adding algorithm takes exactly
$2n - 1 = \Theta(n)$ elementary addition steps to calculate $a + b$.
This is because each digit of $c$ (except the lowest and highest)
requires one step to add the digits from $a$ and $b$ and one step to
add in the carry digit.  The highest digit of $c$ requires no
additional elementary addition steps to compute, and the lowest digit
only requires one elementary addition step, as the carry digit to it
is guaranteed to be 0.

It's not possible to predict exactly the run time of the multiplier
without knowing how many bits of $b$ are set, but the worst-case and
average-case run times are $\Theta(n^2)$ elementary addition steps,
since the $\Theta(n)$ addition algorithm must be run once for every
bit that is set in $b$, and in the worst-case and average-case there
will be $\Theta(n)$ bits set in $b$.  (Of course, the best-case run
time is where $b = 0$, in which case the algorithm uses zero
elementary addition steps.)

\newpage

\end{document}
