\documentclass[11pt]{article}
\usepackage{fullpage,amstex,times}
\setcounter{secnumdepth}{0}

\title{15-451 Algorithms, Spring 1997\\ \textbf{Solutions and Comments for Assignment 1}}
\author{Doug Rohde}
\date{\today}
\begin{document}
\maketitle

\section{Problem 1}

\subsection{$O$, $\Omega$, and $\Theta$}
The purpose of this problem was to make sure we all comprehend the rudiments
of $O$ notation.  Because nearly everything we will do in this course relies
on it, it is crucial that $O$ notation, and its cousins $\Omega$ and $\Theta$,
are well understood.  Therefore, we should begin with a little review.  The
definition of $O$ notation, which is hidden in Section 3.2 of the book, is the
following:
\begin{quote}
\boldmath
{\bf We say a function $g(n)$ is $O(f(n))$ for another function $f(n)$ if
there exist constants $c$ and $N$, such that, for all $n \geq N$, we have
$g(n) \leq cf(n)$.  In other words, for large enough $n$, the function $g(n)$
is no more than a constant times $f(n)$.}
\end{quote}
The first key point is that constant multipliers don't matter.  $100n$ is
still $O(n)$ because we can just choose $c$ to be 101 (actually, 100 would
suffice).  This does not mean, however, that all constants can be ignored.
Numbers in the exponent, for example, are important.  $n^2$ is not $O(n)$.  It
will always be greater than $cn$ for large values of $n$ (specifically, those
larger than $c$).  Only constant multipliers can be thrown out.

However, from this we can conclude that any lower order term added into an
expression can be ignored as well.  Imagine that some function $g(n)$ is
$O(n^2+100n)$.  $100n$ is smaller than $100n^2$, so we can weaken the upper
bound and say that $g(n)$ is also $O(101n^2)$.  However, because constant
multipliers don't matter, we can equally well say that $g(n)$ is $O(n^2)$.  On
the other hand, if $g(n)$ is $O(n^2)$, then it should be clear that $g(n)$ is
also $O(n^2+n)$, because the latter is an even looser upper bound.  Therefore,
$O(n^2+n)$ and $O(n^2)$ are equivalent, and we use the latter for simplicity.
The same argument can be applied to any term that grows slower than a constant
multiple of the fastest growing term in the expression.  Therefore,
$n^4+1000n^3+0.02n^2+6$ is $O(n^4)$.

The book mentions that an exponential function grows faster than a polynomial
function.  Likewise, a polynomial function grows faster than a logarithmic
function.  Here is a partial hierarchy of functions:
\[c < c(\log n)^k < cn^k < c(j^{kn}) < c(n^{kn})\]

As long as $c$ and $k$ are positive and $j > 1$, a function to the right of
another will always grow faster.  Note that $c$ cannot be a function of $n$ or
it is not a constant and cannot be ignored.  $nk^n$ is not $O(k^n)$.  Just as
constants don't matter as multipliers, they also don't matter as the base of a
logarithm because we can change from base $a$ to base $b$ by multiplying by
the constant $log_{b}a$.  Therefore, you can just write $\log$ to mean the
logarithm in any base if there is no need to be more specific.  However, let
us repeat that constants do matter in exponents.  Thus, within a class listed
above, we create higher order functions by increasing $j$ or $k$, but not $c$.

$\Omega$ is essentially the opposite of $O$ notation.  Instead of an upper
bound, $\Omega$ is a lower bound.  We can obtain the definition by replacing
the $g(n) \leq cf(n)$ with a $g(n) \geq cf(n)$ in the definition of $O$
notation above.  Thus, if $g(n)$ is $O(f(n))$, we can say that $f(n)$ is
$\Omega(g(n))$.  If $g(n)$ is $O(f(n))$ and $g(n)$ is $\Omega(f(n))$, $g(n)$
is bounded both above and below by $f(n)$.  Therefore, the two functions grow
at essentially the same rate.  In this case we write $g(n)$ is $\Theta(f(n))$.
It should be clear that in this case, $f(n)$ is also $\Theta(g(n))$.

Rather than writing ``$g(n)$ is $\Theta(f(n))$'', we will often use the
shorthand $g(n) = \Theta(f(n))$.  Likewise for $O$ and $\Omega$ notation.
However, this equal sign should be read as ``is'' and not treated as a true
equivalence because, in the cases of $O$ and $\Omega$, it does not have the
same properties.  For example, we may write $f(n) = O(n^2)$ and $f(n) = O(n)$,
but we cannot conclude that $O(n^2) = O(n)$.  A better notation would be to
consider $O(n)$ to be the {\em set} of all functions which do not increase
faster than $n$.  Then we could express $f(n)$ as $O(n)$ using set member
notation $f(n) \in O(n)$.  Unfortunately, no one does this as far as I know,
so you're better off sticking with ``is'' or ``$=$''.

Finally, to make things complete, we say that $f(n) = o(g(n))$ (pronouned
``little oh'') when $f$ grows strictly slower than $g$.  Concretely, $f(n) =
o(g(n))$ iff
\[\lim_{n \rightarrow \infty} \frac{f(n)}{g(n)} = 0.\]

Similarly, if $f(n) = o(g(n))$ then $g(n) = \omega(f(n))$.  Note that you
can't satisfy both $f(n) = o(g(n))$ and $f(n) = \omega(g(n))$, so there is no
``little theta''.

\subsection{a)}
\[f(n) = 100n+\log n\ \ \ \ \ \ g(n) = n+(\log n)^2\]

Based on the hierarchy above, $\log n$ to any positive power grows slower than
$n$ to any positive power.  In this case, right away we should see that both
$f(n)$ and $g(n)$ are $\Theta(n)$.  To be a little more long-winded, we could
say the following:

For large $n$, $\log n < n$ and $0 < (\log n)^2$.  Therefore, $f(n) <
101n$.  But 101 times $g(n)$ is greater than $101n$, so $f(n) = O(g(n))$.
However, assuming we know that $(\log n)^2 < n$, we know that $g(n) < 2n$.
$f(n)$ is clearly greater than $2n$, so $g(n) = O(f(n))$.  As a result, $f(n)
= \Theta(g(n))$.

\subsection{b)}
\[f(n) = \log n\ \ \ \ \ \ g(n) = \log n^2\]
Well, if you knew that $\log n^2 = 2 \log n$, then it should have been pretty
clear that $f(n) = \Theta(g(n))$.  If you didn't know that, then you should
have derived it from first principles\dots or looked it up in a book.
Whatever seems easiest.

\section{Problem 2}

\subsection{a)}
In general, when we say ``argue'' we are not looking for a formal proof, but
we would like something sufficiently convincing that it would win a bet.
Invariants are always a nice way to approach a problem like this.  A fairly
straightforward invariant in this case is that just before the $k$th print
statement, the array holds the $k$th integer in binary format, with $x_0$
being the low-order end.  Initially the array is all zeros, the little loop
does nothing, $x_0$ is set to 1, and the second little loop does nothing, so
the array correctly holds a 1 in binary.  On each successive pass through the
big loop, the algorithm adds 1 to the number by converting the final sequence
of the form $011\ldots 1$ to $100\ldots 0$.

Finally, it is critical to argue that the algorithm will not terminate until
$2^n$ has been printed, which is true because all numbers less than that have
$x_n = 0$.  The test in the main loop will be true for these numbers.  It is
also critical to argue that it will terminate immediately after printing
$2^n$, which is true because that number has $x_n = 1$.

\subsection{b)}
All the steps within the main loop require a constant amount of time except
the {\bf while} and {\bf for} loops.  We know that upon entering the loop,
$x_n = 0$.  Therefore, the first small loop can run at most $n$ times before
$x_i = 0$.  Each time it runs it does constant work.  The total work in this
loop is therefore $O(n)$.  The second small loop runs exactly the same number
of times as the first loop, so it too does $O(n)$ work.  Therefore, each
iteration of the big loop takes $O(1 + n + n) = O(n)$ time.

\subsection{c)}
Assume, first of all, that the printing procedure takes no time.  This should
not ordinarily be your assumption about such things, but it is necessary for
this proof to be possible.  When the question says ``steps'', it means little
steps, {\em not passes through the main loop}.  In general, when we say
``steps'' we mean ``little constant time operations''.  Thus, ``number of
steps'', ``time'', and ``work performed'' are all equivalent concepts.  If we
ever intend to say ``passes through a loop which does not clearly require
constant time for each pass'', we will say ``iterations of the loop'' or
``passes through the loop'' or talk about the number of times the loop test is
performed.

The key insight to this problem is that most of the time the little loops do
not have to do very much.  Only in the very worst case do they perform $n$
iterations.  All the other operations inside the main loop, including the
test, require constant time for each integer printed.  Therefore, the sum of
all these operations for the $2^n$ integers is $O(2^n)$.  Because we seek to
prove this same bound on the entire algorithm, we can essentially ignore them.
Because the second little loop runs the same number of times as the first
little loop and does constant work in each step, we can ignore it as well.
All that remains to consider is how many times the first little loop will run
for each integer printed.  Here are a few different methods for solving this:

\subsubsection{Method 1}
Every time the previous number printed ends in $0$, the loop does 1 test.
This happens half the time or $2^{n-1}$ times.  When the previous number ends
in $01$, the loop does 2 tests.  This happens 1/4 of the time or $2^{n-2}$
times.  Numbers ending in $011$ occur $2^{n-3}$ times and require 3 tests.
It is easy to see that this is the case by considering how many numbers we
could produce which end in $011$.  This is equal to the number we could create
using the remaining $n-3$ bits, which is $2^{n-3}$.  The total number of tests
is given by the sum:
\[1\cdot 2^{n-1} + 2\cdot 2^{n-2} + 3\cdot 2^{n-3} + \dots + (n-1)\cdot 2^1 + n\cdot 2^0 + n + 1\]

The final $n+1$ is just to be exact and counts the tests performed on the very
last pass through the big loop.  Except for these final terms, this exact
summation happens to be solved on page 46 of the book.  The solution involves
multiplying by 2 and then subtracting off the original terms, which gives the
equivalent expression:
\[2^n + 1\cdot2^{n-1} + 1\cdot2^{n-2} + \dots + 1\cdot 2^1 + 1\]

This, you ought to know, is equal to $2^{n+1} - 1$, which is $O(2^n)$.
Therefore, the total work done in the loops over the course of the entire
algorithm is $O(2^n)$ and the whole thing is $O(2^n)$.

\subsubsection{Method 2}
Another way to approach this problem, like most problems, is via induction.
Induction is especially nice when you have a hint of the bound you're aiming
for.  Some people tried to do induction on the integer being printed.  This
road leads to disaster.  It is possible, however, to do induction on $n$.

In the base case, when $n$ = 0 there is one element in the array, $x_0$. In
this case the small loop does one test, the number 1 is printed and the
algorithm exits.  It therefore runs in $O(1)$ time, which is $O(2^0)$.

Now assume that the algorithm runs in time $T(n-1) = O(2^{n-1})$.  We wish to
prove that it will run in time $T(n) = O(2^n)$ when given the input $n$.  The
algorithm begins exactly the same way for $n$ as it did for $n - 1$, until the
$(n-1)$th bit has become 1.  At this point the algorithm would have halted
when run with $n-1$.  However, when run with $n$ it will start the process
over again.  On the last step, rather than setting the $(n-1)$th bit to 1, it
will be set to 0 and the $n$th bit will be set to 1.  Therefore, the algorithm
takes exactly twice as long as it did with $n-1$, plus some constant factor.
Therefore, we have the expression:
\[T(n) = 2\cdot T(n-1) + k\]

The somewhat lazy way to solve this is to substitute $O(2^{n-1})$ for
$T(n-1)$, giving:
\[T(n) = 2\cdot O(2^{n-1}) + k = O(2^n) + k = O(2^n).\]

Such shortcuts are liable to lead to mistakes, however. Another method is to
expand out the recurrence as follows:
\[T(n) = 2(2(2(\cdots 2(2(k)+k)+k \cdots)+k)+k)+k\]

In multiplying this out, the innermost $k$, which comes from $T(0)$, will be
multiplied by $n$ 2's.  The next $k$ will be multiplied by $(n-1)$ 2's and so
on.  This gives:
\[T(n) = k (2^n + 2^{n-1} +\cdots+1) = k(2^{n+1} - 1) = O(2^n)\]


\subsubsection{Method 3}
Perhaps the cleanest way to solve this problem is by using amortized analysis.
This method may not be covered in depth until later in the course, but this is
such a nice example that it's worth mentioning.  One way to do this is to
imagine storing up {\em credits} and then reclaiming them later.  A credit is
a unit of currency which will pay for 1 constant time step.  If we want to
store a credit someplace, we have to pay a time step for its creation.  But
later on, we can reclaim the credit and perform a step without paying for it.
Essentially, the credit pays for this step.

In this case, imagine putting two credits on a bit every time we change it
from a 0 to a 1.  Initially all the bits are 0 so there are no credits in the
array.  Each time we go through the main loop, we will set one bit to 1.  In
doing so, we will charge ourselves 2 time units for the 2 credits we will
place on that bit.  Therefore, the placing of credits takes constant time for
each number printed.  We are worried about how many times the small loops will
run.  The first loop does a comparison for each low-order bit which is set to
1, plus some constant additional work.  The non-constant operations we can
pay for by taking one credit off those bits (which should have 2 on them).

The second small loop passes over those same bits and sets them to 0.  In
order to pay for this, we will remove the second credit from each bit as we
set it to 0.  When we are done, we have preserved the invariant that all bits
set to 1 have 2 credits and all bits set to 0 have no credits.  Because we
paid for these non-constant operations with credits (which we already bought
when we set the bits to 1), we need not consider the cost of these operations
since they have already been paid for when we placed the credits.

Although this proof could be a bit more rigorous, we have essentially shown
that only a constant number of operations, on average, are performed for each
number printed.  Therefore, the whole algorithm will run in $O(2^n)$ time.
Amortized analysis is a very powerful technique, especially when dealing with
suites of functions based on data structures, such as union-find or
priority-queue operations.


\subsection{d)}
The key to this question is that it is possible for an algorithm to be both
$O(n2^n)$ and $O(2^n)$ because these are just upper bounds.  In this case,
$O(n2^n)$ happens to be a very loose upper bound.

\end{document}