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


\title{6.046 Problem Set 6}
\author{Chris Laas: Section G}
\date{March 28, 2000}

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

\renewcommand{\labelenumi}{(\alph{enumi})}
\renewcommand{\labelenumii}{\arabic{enumii}.}
\NumberProgramstrue
\def\RETURN{\keyword{return}\ }
\def\MOD{\mbox{mod}\ }
\def\text#1{\mbox{ #1 }}
\def\AND{\mbox{\bf\ and }}
\def\OR{\mbox{\bf\ or }}



\begin{document}
\maketitle




\section*{Problem 6-1}

To support the $|Lookup|$ operation, two pieces of data must be added to
each node:

\begin{enumerate}
\item a $|last-access-time|$ value which gives the last time a lookup
operation was performed on that cell
\item a $|min-last-access-time|$ value which is the minimum of all the
$|last-access-time|$s of the nodes in the subtree rooted at that node.
\end{enumerate}

(The ``current'' time must simply be a value which monotonically
increases over subsequent calls to $|Lookup|$.)

The $|last-access-time|$ is maintained by updating the value for the
node in question when it is looked up; thus, maintaining it only adds
$O(1)$ to the run time of the $|Lookup|$ operation.

The $|min-last-access-time|$ can be computed as
$$
\begin{array}{lll}
|min-last-access-time|[|node|]
 = \min \{ & |last-access-time|[|node|], \\
           & |min-last-access-time|[|left|[|node|]], \\
           & |min-last-access-time|[|right|[|node|]] & \}
\end{array}
$$
Thus, since it can be computed only from local information,
$|min-last-access-time|$ can be maintained in a balanced binary tree
without affecting $|Lookup|$'s $O(\lg n)$ performance.

Now, we simply use these values to find the LRU cell whenever we need
to flush a cell: starting at the root, follow the branch with lesser
$|min-last-access-time|$ until we reach a leaf, or a node whose
$|last-access-time|$ is less than the $|min-last-access-time|$ of both
of its subtrees.  This node is the LRU cell, so we delete it.  (Since
we travel only downwards in the tree to search for the LRU cell, we
find it within $O(\lg n)$ steps.)

The algorithm for $|Lookup|$ is summarized as follows:
\renewcommand{\labelenumi}{\arabic{enumi}.}
\begin{enumerate}
\item Search for the cell; if it is in the cache already, return it.
\item If the number of elements in the cache is less than $n$, $|Insert|$
      the cell, and return the new node.
\item Else:  use the above procedure to find the LRU element and
      $|Delete|$ it.  Then $|Insert|$ the new cell, and return this
      new node.
\end{enumerate}
\renewcommand{\labelenumi}{(\alph{enumi})}

Since none of these steps take more than $O(\lg n)$ time, $|Lookup|$
runs in $O(\lg n)$ time.

\newpage





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

\item%(a)

The algorithm to find our ``target'' interval, given an interval tree
$T$ and an interval $[a,b]$, is:

\begin{program}
|Min-Overlapping-Interval|(T, a, b)
\quad\tab |node| \gets |root|[T]
          \WHILE |low|[|node|] > b
                |node| \gets |left|[|node|]
                \IF |node| = |nil|
                   \THEN \RETURN |nil|
                        \untab%
                   \untab%
                \untab%
          \WHILE |node| \neq |nil|                            \label{loop_b}
                \IF |left|[|node|] = |nil| \OR |max|[|left|[|node|]]] < a
                   \THEN \IF |int|[|node|] \text{overlaps} [a,b]
                            \THEN \RETURN |node|
                                 \untab%
                            \untab%
                         |node| \gets |right|[|node|]
                   \ELSE |node| \gets |left|[|node|]
                         \untab%
                   \untab%
                \untab%
          \RETURN |nil|
\end{program}

First, we will show correctness.  If we return $|nil|$ before we reach
line~\ref{loop_b}, then there is no node with $|low|[|node|] \leq b$;
thus, clearly no interval in the tree overlaps $[a,b]$.

Else, at line~\ref{loop_b}, $|node|$ is pointing at a node such that
$|low|[|node|] < b$.  Now, for the loop beginning at
line~\ref{loop_b}, our loop invariant is that the target interval (the
interval in $T$ overlapping $[a,b]$ that has the minimum low endpoint)
is in the subtree rooted at node, if the target exists at all.  This
is certainly satisfied at the outset, since the target interval cannot
be in the rest of the tree (since for the rest of the tree
$|low|[|node|] > b$).  In the loop body:  If there is no left subtree,
or $|max|[|left|[|node|]] < a$, then clearly the target interval is
not in the left subtree.  Since $|int|[|node|]$ is the interval with
the least low endpoint among $|node|$ and $|node|$'s right subtree, if
$|int|[|node|]$ overlaps $[a,b]$, then $|int|[|node|]$ is the target
interval, and so we return it; else, clearly the target is in the
right subtree, so we replace $|node|$ with $|right|[|node|]$ and
continue.  If, on the other hand, there is a left subtree and
$|max|[|left|[|node|]] \geq a$, it is clear that the target is in the
left subtree, so we replace $|node|$ with $|left|[|node|]$ and
continue.  If we ever reach a $|nil|$ subtree (only by following a
right subtree) there is no target interval.

Both loops travel monotonically downward in the tree; since the tree
has finite height, the algorithm must terminate.  This concludes the
proof of correctness.

Finally, we will analyze the run time.  Again, in each loop iteration
of either loop, we travel downward in the tree by one edge.  Thus, the
total run time is bounded by the height of the tree, which, for a
balanced binary tree, is bounded by $O(\lg n)$.  Thus, the run time is
$O(\lg n)$.


\item%(b)

It's not entirely clear how to solve this without modifying the tree.
A simple algorithm to do this, which does modify the tree, is:

\begin{program}
|All-Overlapping-Intervals-Destructive|(T, a, b)
\quad\tab |node| \gets |Min-Overlapping-Interval|(T, a, b)
          \WHILE |node| \neq |nil|
                |Print|(|int|[|node|])
                |Delete|(T, |node|)
                |node| \gets |Min-Overlapping-Interval|(T, a, b)
\end{program}

Since $|Min-Overlapping-Interval|$ executes exactly $k+1$ times, and
each execution takes $O(\lg n)$ time, the run time is bounded by
$O((k+1) \lg n)$.


Alternatively, another algorithm does it without modifying the tree:
\begin{program}
|All-Overlapping-Intervals-In-Subtree|(|node|, a, b)
\quad\tab \IF |int|[|node|] \text{overlaps} [a,b]
              \THEN |Print|(|int|[|node|])
                   \untab%
              \untab%
          \IF |left|[|node|] \neq |nil| \AND |max|[|left|[|node|]] \geq a
              \THEN |All-Overlapping-Intervals-In-Subtree|(|left|[|node|], a, b)
                   \untab%
              \untab%
          \IF |right|[|node|] \neq |nil| \AND |low|[|node|] \leq b
              \THEN |All-Overlapping-Intervals-In-Subtree|(|right|[|node|], a, b)
                   \untab%
              \untab%
\end{program}

\begin{program}
|All-Overlapping-Intervals-Recursive|(T, a, b)
\quad\tab |node| \gets |root|[T]
          \WHILE |low|[|node|] > b
                |node| \gets |left|[|node|]
                \IF |node| = |nil|
                   \THEN \RETURN |nil|
                        \untab%
                   \untab%
                \untab%
          |All-Overlapping-Intervals-In-Subtree|(|node|, a, b)
\end{program}

This is a modified preorder traversal of the tree, pruning subtrees
which could not contain intervals which overlap $[a,b]$.

$|All-Overlapping-Intervals-Recursive|$ never visits a node twice, so
it clearly runs in $O(n)$ time.  It's not clear how to prove it is
bounded by $O((k+1) \lg n)$, though.  It seems likely to prune enough
subtrees to bring it down to this bound, however.


\end{enumerate}
\newpage



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

\item%(a)

For $n = 2^k$, for $k$ integer, we can construct the sequence of $n/2$
increments (bringing the counter value to $2^{k-1}$) followed by an
alternating sequence D, I, D, I, D, \dots of $n/2$ operations ($n/4$
decrements and $n/4$ increments).  This second half of the sequence
flips $k$ bits per operation, resulting in a total of $kn/2$ bit-flips
for that half-sequence.  Thus, this sequence results in
$\Omega(kn) = \Omega(n \lg n)$ bit-flips, total; thus, the amortized
cost of each operation is $\Omega(\lg n)$.


\item%(b)

In the best case, only one trit changes (for either operation), and so
the best-case cost is $\Theta(1)$.

However, the worst-case increment is of
$t_{k-1}t_{k-2}\cdots{}t_1t_0 = 22\cdots{}22 \to 111\cdots{}11$,
which changes $k+1$ trits; likewise, the worst-case decrement is of
$t_{k-1}t_{k-2}\cdots{}t_1t_0 = 100\cdots{}00 \to 011\cdots{}11$,
which likewise changes $k$ trits.  Thus, the worst-case cost is
$\Theta(k)$.

In general, the number of trits changed is equal to the $t$, the
number of lower-order trits equal to 2 (in the case of incrementing)
or 0 (in the case of decrementing), plus 1 for the final
non-overflowing trit.


\item%(c)

Intuitively, we want to ``pay'' a little extra when we change a bit
from 1 to 0 or 2, so that we can then use that ``credit'' to pay for
resetting the bit to 1 later on.

We will define a potential function $\Phi$ for the counter.  Let
$\Phi$ by the number of trits equal to 0 or 2; of course, we ignore
the (infinite) number of leading zeros.  Clearly, $\Phi$ is always
positive.  Now let us consider the cases for operation \#$i$:

\begin{enumerate}
\item%1
The $i$th operation is an increment.  Suppose it resets $t_i$ trits
from 2 to 1; it also increments trit \#$t_i$.  Thus, the actual cost
is $t_i+1$ trit-changes.
  \begin{enumerate}
  \item If trit \#$t_i$ goes from 0 to 1, then the change in potential is
        $\Delta \Phi = -1 - t_i$.
  \item Else, trit \#$t_i$ goes from 1 to 2, and $\Delta \Phi = 1 - t_i$.
  \end{enumerate}

\item%2
The $i$th operation is a decrement.  Suppose it resets $t_i$ trits
from 0 to 1; it also decrements trit \#$t_i$.  Thus, the actual cost
is $t_i+1$ trit-changes.
  \begin{enumerate}
  \item If trit \#$t_i$ goes from 2 to 1, then $\Delta \Phi = -1 - t_i$.
  \item Else, trit \#$t_i$ goes from 1 to 0, and $\Delta \Phi = 1 - t_i$.
  \end{enumerate}
\end{enumerate}

Now, using $\hat{c}_i = c_i + \Delta \Phi$, we get the amortized costs for
each case:

\begin{enumerate}
\item \begin{enumerate}
      \item $\hat{c}_i = 0$
      \item $\hat{c}_i = 2$
      \end{enumerate}
\item \begin{enumerate}
      \item $\hat{c}_i = 0$
      \item $\hat{c}_i = 2$
      \end{enumerate}
\end{enumerate}

From this it is clear that the amortized cost per operation is $O(1)$.

\end{enumerate}
\newpage



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

\item%(a)

If we have an optimal shelving of books, then the shelving of all the
books on all the shelves except the last shelf is optimal.  For,
assume that it is not optimal.  Then we can find a shorter
(``better'') shelving of those books, and then add the last shelf and
its books back on; then, we have a better shelving of all the books
than the original shelving.  But, since the original shelving was
posited to be optimal, we have a contradiction.

Thus, in mathematical notation, if we say that $H_i$ is the minimal
height of a shelving of books $1 \rdots i$, we can state the above as
the recurrence:

$$ \begin{array}{lll}
H_i = \min \{ & H_{j-1} + \max \{ h[j], h[j+1], \dots, h[i] \} \\
              & \text{\bf such that} 1 \leq j \leq i \\
              &             \AND w[j] + w[j+1] + \dots + w[i] \leq W & \}
   \end{array} $$

(With, of course, $H_0 = 0$.)

More concisely,
$$ H_i = \min \{ H_{j-1} + |height|(j,i)
                 \text{\bf such that} 1 \leq j \leq i
                 \AND |width|(j,i) \leq W \} $$
where $|height|(j,i) = \max_{j \leq k \leq i} h[k]$ is the height of a
shelf containing books $j \rdots i$, and
$|width|(j,i) = \sum_{k=j}^i w[k]$ is the width of the shelf.


\item%(b)

The algorithm's pseudocode is as follows:

\begin{program}
|Find-Minimum-Height|(h[1 \rdots n], w[1 \rdots n], W)
\quad\tab H[0] \gets 0
          \FOR i \gets 1 \rdots n
              H[i] \gets \infty
              |width| \gets 0
              |height| \gets 0
              j \gets i
              \WHILE j > 0 \AND |width| + w[j] \leq W
                    |width| \gets |width| + w[j]
                    |height| \gets \max(|height|, h[j])
                    H[i] \gets \min(H[i], H[j-1] + |height|)
                    j \gets j - 1
                    \untab%
              \untab%
          \RETURN H[n]
\end{program}

The algorithm clearly terminates, because the outer loop executes
exactly $n$ times, and the inner loop executes at most $n$ times per
outer loop.

This is a direct implementation of the recursion formula, which we
derived in (a).  We know that $H[i]$ depends only on $H[j]$ for
$j < i$; thus, we can go forward filling the array $H$ in in order.
We take the minimum of all valid
$H[j-1] + |height|(j,i) = H[j-1] + \max \{ h[j], h[j+1], \dots, h[i] \}$
to produce $H[i]$, where a ``valid'' $j$ is one such that the books
$j \rdots i$ will fit (widthwise) on one shelf:
$w[j] + w[j+1] + \dots + w[i] \leq W$.  At the end, $H[n]$ is the
minimum height of a shelving of books $1 \rdots n$.


\item%(c)

Since the outer loop executes exactly $n$ times, and the inner loop
executes at most $n$ times, the run time is bounded by $O(n^2)$.  We
can further refine this by defining $k$ as the maximum number of
sequential books (among $1 \rdots n$) that will fit on a shelf: since
the inner loop executes at most $k$ times, the run time of the
algorithm is $O(kn)$.  (For many classes of inputs, $k$ will be a
small constant, making the algorithm have essentially linear run
time.)


\end{enumerate}
\newpage



\section*{Problem 6-5}

Let us define the potential $\Phi$ to be the number of leaves minus
the number of internal nodes.  For a given number of leaves, the
maximum number of internal nodes occurs when each internal node has
two children; in this case, the number of internal nodes equals the
number of leaves minus 1.  (If the number of leaves is not a power of
2, it is not possible for each internal node to have two children;
however, in this case the difference between number of leaves and
number of internal nodes is even greater.)  Thus, for any valid 2-3
tree, $\Phi \geq 1 > 0$.

Every insertion of a leaf increases $\Phi$ by 1, but every split
decreases $\Phi$ by 1.  Thus, after $n$ insertions (involving, say,
$k$ splits), $\Phi(n) = n - k$.  Thus, since $\Phi > 0$, we see that
$n > k$.  Thus, the total number of splits, after $n$ insertions, is
at most $cn$, for $c = 1$.

\newpage



\end{document}
