\documentstyle[11pt,handout]{article}
\begin{document}
\input{macros}
\input{epsf}
\input{/home/rraj/Courses/3390/S99/macros/localmacros}
\thispagestyle{empty}
\setlength{\parindent}{0pt}
\setlength{\parskip}{1.8ex}

\newcommand{\T}{{\cal T}}
\newcommand{\exmax}{{\sc Extract-Max}}
\newcommand{\heapify}{{\sc Heapify}}
\newcommand{\ins}{{\sc Heap-Insert}}
\newcommand{\hgt}[1]{\mbox{{\em height}}[x]}

\head{3390}{Analysis of Algorithms}{Spring 1999}{7 May 1999}{15}

\begin{center}
\Large{\bf Sample Solution for Problem Set 2}
\end{center}

\bigskip

{\bf 1. (3 + 3 + 9 = 15 points)}\hs Consider a set $S$ of $n$ distinct numbers
given in unsorted order.  Each of the following three problem parts asks you
to give an algorithm to determine two distinct numbers $x$ and $y$ that
satisfy a stated condition.  For each part, describe your algorithm and then
briefly justify the correctness and the running time of the algorithm.
\begin{enumerate}
\item
In $O(n)$ time, determine $x, y \in S$ such that $|x - y|$ is maximum.

{\bf Answer:} The two numbers that are farthest apart are the maximum and the
minimum numbers in $S$.  Therefore, find the maximum $M$ and the minimum $m$
of $S$.  This takes $O(n)$ time.  Return $M$ and $m$.

\item
In $O(n \lg n)$ time, determine $x, y \in S$ such that $|x - y|$ is minimum.

{\bf Answer:} The two numbers $x$ and $y$ such that $|x - y|$ is minimum must
be consecutive numbers in the sorted order (otherwise, we can replace $x$ by a
number $z$ that lies between $x$ and $y$ and thus obtain $|z - y| < |x - y|$,
leading to a contradiction).  So, we first sort the $n$ numbers.  This takes
$O(n \lg n)$ time.  Then, we scan through the sorted list, keeping track of
the minimum difference between consecutive numbers, and return the two
consecutive numbers that are closest.  This scan takes $O(n)$ time.
Therefore, total running time is $O(n \lg n)$.

\item
Let $M$ and $m$ denote the maximum and minimum numbers in $S$, respectively.
In $O(n)$ time, determine $x, y \in S$ such that $x$ and $y$ appear
consecutively in the sorted order and
\[|x - y| \ge \frac{1}{n-1}(M - m).\]
That is, determine any two numbers that appear consecutively in the sorted
order and are at least as far apart as the average distance between
consecutive numbers in the sorted order.

{\bf Answer:} We first give an algorithm that almost works.  It will return
two numbers $x, y \in S$ such that $x$ and $y$ appear consecutively in the
sorted order and 
\[|x - y| \ge \frac{1}{n}(M - m).\]
(Note the difference: we have an $n$ in the denominator instead of the $n-1$.)

The basic idea is to partition around the middle of the range $[m, M]$ and
then essentially recurse on the partition that has smaller size.  We first
consider the base case where $n = 2$.  In this case, we just return the two
elements.

If $n > 2$, then we first find the maximum $M$ and the minimum $m$ in $S$.
This takes $O(n)$ time.  Let $\mu$ denote the average $(M + m)/2$ of the two
numbers.  We partition the set $S$ into two sets $S_1$ and $S_2$ such that
every element in $S_1$ is at most $\mu$ and every element in $S_2$ is greater
than $\mu$.  Since the total number of elements in $S$ is $n$, either $S_1$ or
$S_2$ has at most $\lfloor n/2 \rfloor$ elements.

We now consider three cases.  The first case is when $|S_1| < |S_2|$.  In this
case let $S'$ equal $S_1$ together with the smallest number in $S_2$, and we
solve the given problem recursively on $S'$.  That is, if $n'$, $m'$, and $M'$
denote the number of elements, minimum, and maximum, respectively in $S'$,
then we recursively find two numbers $x$ and $y$ in $S'$ such that $x$ and $y$
appear consecutively in the sorted order of $S'$ and satisfy the inequality:
\[ |x - y| \ge \frac{1}{n'}(M' - m').\]
We can prove the correctness of this case by showing that $\frac{1}{n'}(M' -
m') \le \frac{1}{n-1}(M -m)$.  To show this, we note that $n' \le \lceil n/2
\rceil$, $m' = m$, and $M' \ge (M + m)/2$.  So we obtain:
\begin{eqnarray*}
\frac{1}{n'-1}(M' - m') 
& \ge & \frac{(M + m)/2 - m}{\lceil n/2 \rceil -1}\\
& \ge & \frac{M - m}{2(\lceil n/2 \rceil -1)}\\
& \ge & \frac{M - m}{n - 1}.
\end{eqnarray*}

The second case is when $|S_2| < |S_1|$.  This case is symmetric to the above.

The final case is when $|S_1| = |S_2| = n/2$.  In this case, we can't just
recurse on any of the two sets because it is possible that there is a wide gap
between the largest element $M_1$ of $S_1$ and the smallest element $m_2$ of
$S_2$, and we may miss this solution if we recurse on either $S_1$ or on
$S_2$.  So we first check the difference $m_2 - M_1$.  If $m_2 - M_1 \ge (M -
m)/(n-1)$, then we return $M-1$ and $m_2$ and we are done.  Otherwise, we
determine which of the two numbers is closer from $\mu$.  If $M_1$ is closer,
then we recurse on $S_1$; otherwise, we recurse on $S_2$.  We first note that
the calculation of $M_1$ and $m_2$ takes $O(n)$ time.  We now show that if
$m_2 - M_1 < (M - m)/(n-1)$, then our recursive step is correct.  For this we
only consider the case in which $M_1$ is closer to $\mu$.  In this case, we
have $M_1 \ge (M + m)/2 - (M - m)/(2(n-1))$.  For correctness, we need to show
that $\frac{M_1 - m}{(n/2) - 1}$ is at least $\frac{M - m}{n-1}$.  The proof is
as follows.
\begin{eqnarray*}
\frac{M_1 - m}{(n/2) - 1} 
& \ge & \frac{(M + m)/2 - (M - m)/(2(n-1)) - m}{(n/2) - 1}\\
& = & \frac{M(n-2)/(2(n-1)) - m(n-2)/(2(n-1))}{(n/2) - 1}\\
& = & \frac{M(n-2)/(n-1) - m(n-2)/(n-1)}{n-2}\\
& = & \frac{M - m}{n-1}.
\end{eqnarray*}

We now consider the running time of the algorithm.  We first note that $T(2) =
O(1)$.  Since the set we recurse on is of size at most $\lceil n/2 \rceil$,
the recurrence relation is as follows:
\[ T(n) \le T(\lceil n/2 \rceil) + O(n).\]
If we ignore the ceiling, then we can use case~3 of the master theorem and
obtain $T(n) = O(n)$.  We can also get a more precise proof using the
substitution method.

\end{enumerate}

{\bf 2. (5 $\times$ 4 = 20 points)}\hs Problem~7--2, page 152.

\begin{itemize}
\item[{\bf (a)}] 
A $d$-ary heap can be represented by an array as follows: Let $A[1]$ be the
root.  For each $i$ and $1 \le j \le d$, the $j$th child of $A[i]$ is given by
$A[(i-1)d + j + 1]$.  We can prove the correctness by induction on $i$.  For
the base case, we take $i = 1$.  Clearly, the $d$ children of $A[1]$ are
$A[2]$ through $A[d + 1]$, thus establishing the base case.  For the induction
step, all we need to check is that the $d$ children of $A[i]$ come immediately
following the $d$ children of $A[i-1]$, which is true according to our formula.

The parent of $A[i]$ is given by $A[\lceil (i-1)/d \rceil]$; this directly
follows from the fact that if $A[k]$ is the parent of $A[i]$, then $i$ is of
the form $(k-1)d + j + 1$, implying that $\lceil (i - 1)/d \rceil = k$.

\item[{\bf (b)}]
The number of nodes at level $1$ is $1$, at level $2$ is $d$, at level $3$ is
$d^2$, and in general, at level $i$ is $d^{i-1}$, except the last level $h$,
where it may be between $1$ and $d^{h-1}$.  We thus have:
\begin{eqnarray*}
1 + d + d^2 + \ldots + d^{h-2} \le & n & \le 1 + d + d^2 + \ldots + d^{h-1}\\
\frac{d^{h-1} - 1}{d-1}  \le & n & \le  \frac{d^{h} - 1}{d - 1}\\
d^{h-1} - 1 \le & n(d - 1) & \le d^h - 1.
\end{eqnarray*}
It thus follows that $\log_d(nd - d + 1) \le h \le \log_d(nd - d + 1) + 1$,
which implies that $h = \Theta(\log_d n) = \Theta(\lg n/(\lg d))$.

\item[{\bf (c)}] The \exmax\ routine can be the same as the routine described
in text on page 150 for $d = 2$.  The main procedure that needs to be changed
is \heapify.  In the \heapify\ routine, rather than just finding the largest
among a node and its two children, we find the largest among the node and its
$d$ children.  This takes $O(d)$ time.  Therefore, the \heapify\ routine will
take $\Theta(d \log_d{n})$ time.  The running time of \exmax\ will also be
$\Theta(d \log_d{n})$.

\item[{\bf (d)}]
Exactly the same algorithm as the one given on page~150 will work since we
only traverse the parent pointers.  Note that the parent pointer has been
defined according to part~(a).  The running time of \ins\ is $\Theta(h) =
\Theta(\log_d n)$. 

\item[{\bf (e)}]
When we increase any key $A[i]$, then the heap property is preserved in the
subtree rooted at $A[i]$.  However, the heap property may be violated between
$A[i]$ and its parent.  We can use a procedure similar to \ins\ in which we
move the tree and reestablish the heap property as we go on.  

If $A[i] \ge k$, then we do nothing.  Otherwise, we set $A[i] = k$, and then
execute lines~3 to~6 of {\sc Heap-Insert} given on page 150 of text.
\end{itemize}

{\bf 3. (4 points)}\hs Give a constant time algorithm to find the fifth
largest element from a heap of $n$ distinct elements.

{\bf Answer:} We give an iterative procedure for finding the $i$th largest
element.  The largest element is simply $A[1]$.  The second largest element in
the heap is the largest among the two children of the largest element of $A$.
For any $i \ge 1$, let $X_i$ denote the set of the $i$ largest elements of $A$
and $Y_i$ denote the children of the first $i$ largest elements.  For example,
$X_1 = \{A[1]\}$ and $Y_1 = \{A[2], A[3]\}$.  As another example, if it turns
out that $A[3]$ is the second largest element, then $X_2 = \{A[1], A[3]\}$ and
$Y_2 = \{A[2], A[6], A[7]\}$.

It can be shown by induction on $i$ that the $i$th largest element of $A$ is
the largest element of the set $Y_{i-1} \setminus X_{i-1}$.  In order to find
the 5th largest element, we iteratively find $X_1$, $Y_1$ through $X_4$, $Y_4$,
and then find the largest element in $Y_4 \setminus X_4$.  Since each of these
sets consists of only a constant number of elements, the total running time of
the algorithm is a constant.

{\bf 4. (4 $\times$ 4 = 16 points)}\hs Problem~13--1, page 259.

\begin{itemize}
\item[(a)] If we use {\sc Tree-Insert} to insert $n$ items with identical
keys, then the first item will form the root.  Then, every subsequent item
will be added as a right child of the rightmost leaf of the present tree, and
will thus form the rightmost leaf of the tree.  This is because according to
lines~5--8 of the code given on page 251 of text, the search will always
proceed to the right when we have an identical key.

Thus, the insertion of the first item will traverse $0$ nodes, the insertion
of the second item $1$ node, the insertion of the $i$th item $i - 1$ nodes.
Therefore the total running time is $\Theta(1 + 2 + \ldots + n - 1) =
\Theta(n^2)$. 

\item[(b)] We will show that the binary tree obtained at any time is a
balanced binary time.  More precisely, we will show the following claim: (A)
for any $i$, the items $2^i + 1$ through $2^{i+1}$ form the $2^i$ nodes at
depth $i$ of the tree.  It is then easy to calculate the total running time
$T(n)$ of the insertion of $n$ items as follows.
\[
T(n) = \Theta(\sum_{0 \le j \le n} \lfloor \lg j \rfloor) = \Theta(n \lg n).
\]

We now prove claim (A).  The proof is by induction on $i$.  For the base case,
we take $i = 0$.  Clearly item $1$ forms the root of the tree; therefore, the
base case is trivial.  For the induction step, consider the items $2^i + 1$
through $2^{i+1}$.  It follows from the induction hypothesis that the binary
tree $T$ that we have just prior to the insertion of these $2^i$ items is a
complete binary tree of depth $i - 1$.  We will now show that the $2^i$ items
numbered $2^i + 1$ through $2^{i+1}$ form the $2^i$ nodes (leaves) at depth
$i$.

We show the above claim by establishing the following claim: (B) for any $0
\le j < i$, the number of insertions among the items $2^i + 1$ through
$2^{i+1}$ that take place in any subtree rooted at a node $u$ of $T$ at level
$j$ is exactly $2^{i - j}$.  The proof is by induction on $j$.  The base case,
$j = 0$, is trivial since all of the $2^i$ items are inserted into the tree.
For the induction step, consider a node $u$ at depth $j$.  By the induction
hypothesis, we know that the number of items that are inserted in the subtree
rooted at the parent of $u$ is exactly $2^{i - j + 1}$.  By the definition of
the insertion routine, we know that the parent of $u$ alternates between
sending items to the left and items to the right.  Therefore, half of the
items enter $u$ and the other half its sibling.  We thus obtain that the
number of items inserted into the subtree rooted at $u$ is exactly $2^{i -
j}$.  This completes the proof of claim (B).

It follows from our proof of claim (B) that at depth $i$, exactly one item is
inserted at any node.  Therefore, the $2^i$ items form the $2^i$ nodes at
depth $i$.  This completes the proof of claim (A) and hence the main result.
 
\item[(c)] This part depends on how the list of equal keys is maintained at
any node.  Here we assume that it is maintained as a linked list and insertion
is done by simply inserting at the head of the list.  In this case, the
insertion of $n$ items with identical keys will result in all items being
inserted to a single list at the root node.  Since each insertion will take
$O(1)$ time, the running time will be $O(n)$ time.

\item[(d)] The worst case for the randomized insertion technique is the same
as for part (a).  This is because there is a finite probability that every
``random'' choice turns out to be ``go to right.''  Therefore, the worst case
running time is $\Theta(n^2)$.  On average, however, we would expect the final
tree to be roughly balanced, suggesting that the expected running time is
$\Theta(n\lg n)$.  A very nice connection between such a randomly built binary
search tree and randomized quicksort is developed in Problem~13--3, page 260,
of text.  The reader is encouraged to go through the problem.  Here, we give
an alternative shorter proof of the desired claim. 

We first establish the lower bound.  In an $n$-node binary tree, how many
nodes have depth less than $(\lg n)/2$?  It is at most $2^{(\lg n)/2} =
\sqrt{n}$.  Thus, at least $n - \sqrt{n}$ nodes were inserted at depth $(\lg
n)/2$ or larger.  This implies that the total running time for insertion is at
least $(n - \sqrt{n})(\lg n)/2 = \Omega(n \lg n)$.

Our upper bound proof will proceed by placing a probabilistic bound on the
height of the tree.  We have seen above that the height of the tree is at
least $(\lg n)/2$.  For a perfectly balanced tree, the height is $\lfloor \lg
n \rfloor$.  What is the probability that after inserting $n$ items with
identical keys, we have a path of length $c \lg n$, where $c$ is some large
constant?  We will now show that if $c$ is sufficiently large, then this
probability is very small.

A specific path of length $c \lg n$ can be obtained only if the $c \lg n$
items involved take the appropriate turns when they are inserted.  This
probability is $(1/2)\cdot(1/2)^2\cdot(1/2)^3\ldots (1/2)^{c\lg n} \le
(1/2)^{(c^2\lg^2n)/2}$.  For each path we have ${n \choose c\lg n}$ choices
for selecting the items that form the path.  And we have $2^{c \lg n}$ such
paths.  Therefore, the probability of having any path of length $c \lg n$ is
at most
\begin{eqnarray*}
2^{c \lg n} {n \choose c \lg n} \left(\frac{1}{2}\right)^{(c^2 \lg^2 n)/2}.
\end{eqnarray*}
If we set $c = 4$, we obtain that the probability of having any path of length
$4 \lg n$ is at most 
\begin{eqnarray*}
2^{4 \lg n} {n \choose 4 \lg n} \left(\frac{1}{2}\right)^{8 \lg^2 n}
& \le & 2^{4 \lg n} n^{4 \lg n} \left(\frac{1}{2}\right)^{8 \lg^2 n}\\
& \le & \left(\frac{1}{2}\right)^{4 \lg^2 n}\left(\frac{1}{2}\right)^{ 8\lg^2 n - 4\lg n}\\
& \le & \left(\frac{1}{2}\right)^{ 4\lg^2 n - 4\lg n}\\
& \le & \left(\frac{1}{2}\right)^{\lg n}\\
& \le & \frac{1}{n}.
\end{eqnarray*}
Thus, the probability that the height of the final tree is at most $4 \lg n$
is at least $1 - 1/n$.  And with probability at most $1/n$, the height is
bigger than $4 \lg n$ but can be at most $n$.  

Therefore, by the definition of the expectation of a random variable, the
expected running time of each insertion is at most $(1 - 1/n)4 \lg n + (1/n)n
= O(\lg n)$.  The expected total running time is thus at most $n \cdot O(\lg
n) = O(n \lg n)$.
\end{itemize}

{\bf 5. (5 + 7 + 10 + 8 = 30 points)}\hs Problem~19--2, page 399.

\begin{itemize}
\item[(a)] We need to maintain the field $\hgt{x}$ of a node $x$ without
affecting the asymptotic performance of searching, insertion, and delete.  We
first observe that the search return does not modify the tree and hence does
not change the height.  For the insertion and delete routines, first consider
the non-root nodes.  The only changes to these nodes are the ``split'' and
``merge'' routines.  In either case, the height of the node does not change.
In fact, the {\em only}\/ node whose height could possibly change in the tree
is the root node.  If we split the root to create a new root and two siblings,
we set the height of the two siblings to the height of the original root and
the height of the new root to one more than the height of the original root.
On the other hand, if we merge the root and its two siblings to form one root,
then we set the height of the new root to one less than the height of the old
root.  Clearly, these operations take $O(1)$ time and hence do not affect the
asymptotic performance of insertion and delete.

\item[(b)] Without loss of generality, we can assume that $h' \le h''$.  The
main challenge in this part is to put together the tree $T'$, a node
containing key $k$, and the tree $T''$ so that the final tree is a valid 2-3-4
tree.  The key idea is to make use of the fact that all the keys in $T'$ are
less than $k$ and all the keys in $T''$ are greater than $k$.  Now in order to
obtain a single tree, we can insert $k$ together with $T'$ at an appropriate
level of $T''$.  We do this as follows.

We insert the key $k$ into tree $T''$ but do not proceed all the way to a
leaf.  Instead we only go down to level $h' + 1$.  Note that since the
traversal during the insertion routine ensures that when we arrive at a node
it is not full, it follows that there is room for the key $k$ at the leftmost
node of level $h' + 1$.  We insert the key $k$ as the leftmost key at this
node and set the leftmost child of this node to be the root of the tree $T'$.
It is easy to see that the tree thus obtained is a valid 2-3-4 tree.
Moreover, since we only go down to height $h' + 1$, the number of links
traversed is at most $h'' - h' - 1 = O(h'' - h')$.

\item[(c)] Consider the path $p$ from the root of $T$ to a given key $k$.  Let
$u_1$, $u_2$, \ldots, $u_m$ be the nodes along the path where $p$ proceeds to
the the second, third, or fourth child.  See figure below.  We now define
$T'_{i-1}$ and $k_i$ for each $i > 0$.  Consider one of the nodes $u_i$.  We
consider three cases.  The first case is when $p$ proceeds to the second child
of $u_i$.  In this case, we set $T'_{i-1}$ to be the first (or the leftmost)
subtree of $u_i$ and $k_i$ to be the first (or leftmost) key of $u_i$.  The
second case is when $p$ proceeds to the third child of $u_i$.  In this case,
we set $T'_{i-1}$ to be the tree consisting of the first key of $u_i$ as the
root of $T'_{i-1}$ and the first and second subtrees of $u_i$ as the two
subtrees under the root of $T'_{i-1}$.  We set $k_i$ to be the second key of
$u_i$.  We can define $T'_{i-1}$ and $k_i$ for the third case similarly.
Finally, we also need to define $T_m$.  This is the 2-3-4 subtree formed by
the keys to the left of $k$ in the node where $k$ resides.

\begin{figure}[htb]
\centerline{\epsfxsize = 4.4 in \epsffile{234-tree.eps}}
\end{figure}

It is easy to see from the definition that every key in $T'_{i-1}$ is less
than $k_i$ since $k_i$ is always to the right of $T'_{i-1}$.  We now show that
$k_i$ is less than every key in $T'_{i}$.  The main point is that at node
$u_{i}$ the path proceeds to the right of the key $k_{i}$.  Therefore, the
subtree $T'_i$ lies in a subtree that is to the right of $k_{i}$.  This
implies that every key in $T'_i$ is greater than $k_{i}$.  

The height of $T'_{i-1}$ is greater than the height of $T'_{i}$ since $u_i$ is
higher than $u_{i+1}$.  

The path $p$ also partitions $S''$ in a similar way.  The structure of the
partitioning is symmetric to the above structure defined for $S'$.  We have to
simply interchange ``left'' and ``right'', and $>$ and $<$ in the above
argument.  We obtain the following claim: $p$ breaks $S''$ into a set of trees
$\{T''_0, T''_1, \ldots, T''_m\}$ and a set of keys $\{k''_1, k''_2, \ldots,
k''_m\}$, where, for $i = 1, 2, \ldots, m$, we have $y > k''_i > z$ for any
keys $y \in T''_{i-1}$.  The relationship between the heights of $T''_{i-1}$
and $T''_i$ is the same as before.

\item[(d)] We first find the path $p$ from the root to the key $k$.  As we
perform the search, we also compute the tree sets $\T' = \{T'_0, T'_1, \ldots,
T'_m\}$ and $\T'' = \{T''_0, T''_1, \ldots, T''_m\}$ and the key sets $K' =
\{k'_1, k'_2, \ldots, k'_m\}$ and $K'' = \{k''_1, k''_2, \ldots, k''_m\}$ as
indicated in part~(c).  The entire process takes $O(\lg n)$ time.  We now need
to assemble the trees in $\T'$ (resp., $\T''$) together with the keys in $K'$
(resp., $K''$) to obtain a single 2-3-4 tree $T'$ (resp., $T''$).

We perform this assembly operation as follows.  We first perform a join
operation over trees $T'_{m-1}$, $T'_m$, and the key $k'_m$.  Clearly, the
conditions of the join are satisfied due to proof of part (c).  Therefore,
such a join can be performed in $O(h'_{m-1} - h'_m)$ time, where $h'_i$ denotes
the height of tree $T'_i$.  Moreover, the height of the resultant 2-3-4 tree
is at most $h'_{m-1} + 1$, which is at most $h'_{m-2}$, the height of
$T'_{m-2}$.  We now join the resultant tree with $T'_{m-2}$ and the key
$k'_{m-1}$.  Again the running time of the join is $O(h'_{m-2} - h'_{m-1})$
and the height of the resultant tree is at most $h'_{m-2}$.  And we repeat
this procedure until we have joined tree $T'_0$.  The final tree thus obtained
is $T'$.  In general, the $i$th join operation consists of joining the tree
obtained after join $i - 1$ with tree $T'_{m - i}$ and key $k'_{m-i+1}$.  The
running time of the $i$th join is $O(h'_{m-i} - h'_{m-i+1})$.  Therefore the
total running time of the sequence of $m$ joins that results in $T'$ is
\[
O\left(\sum_{1 \le i \le m} (h'_{m - i} - h'_{m-i+1})\right) = O(h'_0 - h'_m) =
O(\lg n).
\]

The assembly of the other set of trees and keys (the $T''_i$s and the
$k''_i$'s) can be done in a similar manner to yield $T''$.  This process also
takes $O(\lg n)$ time.  This completes the split operation.
\end{itemize}

{\bf 6. (15 points)}\hs Consider a set of $n$ rectangular paving stones where the
$i$th stone is $l_i$ units long and $w_i$ units wide, $l_i\geq w_i\geq 1$.
Assume that paving stone $i$ can be stacked on top of paving stone $j$ iff
$l_i\leq l_j$ and $w_i\leq w_j$.  Give an efficient algorithm for computing
the maximum number of paving stones that can be stacked together, and analyze
the asymptotic running time of your algorithm.  ({\em Hint:}\/ Use dynamic
programming.)

{\bf Answer:} We provide two algorithms for this problem.  The first one
is a reduction to the longest common subsequence (LCS) problem that we studies
in class.  The second is a more traditional dynamic programming approach.
\begin{itemize}
\item {\bf Algorithm~1:} Using LCS, we can solve the given paving stones
problem as follows.  We first sort the stones according to their lengths in
nondecreasing order.  If there are any ties, we break them arbitrarily, say
according to the number of the stone.  Let $S_\ell$ be the list of stones thus
obtained.  We then sort the stones by their widths.  We break ties in the same
manner as we broke them for lengths.  Let $S_w$ is the sorted list of stones
thus obtained.  Our algorithm is now to simply return the length of the
longest common subsequence of $S_\ell$ and $S_w$.

The running time of the algorithm is $O(n^2)$ since sorting takes $O(n \lg n)$
time and {\sc Lcs-Length} takes $O(n^2)$ time.  The correctness of the
algorithm follows from the following two lemmas.
\begin{Lemma}
\label{lem:1}
Every common subsequence of $S_\ell$ and $S_w$ is a sequence of stones that
can be stacked together.
\end{Lemma}
\begin{Proof}
Let $s_1$, $s_2$, \ldots, $s_i$, \ldots, $s_k$ denote a sequence of $k$ stones
that form a common subsequence of $S_\ell$ and $S_w$.  It follows from the
length-sortedness of $S_\ell$ that the length of stone $s_i$ is at most the
length of $s_{i+1}$ for any $i$ between $1$ and $k-1$.  Similarly, the width
of stone $s_i$ is at most the width of $s_{i+1}$ for any $i$ between $1$ and
$k-1$.  Therefore, stone $s_i$ can be stacked on top of stone $s_{i+1}$.
Thus, any common subsequence of $S_\ell$ and $S_w$ yields a sequence of stones
that can be stacked together.
\end{Proof}

\begin{Lemma}
\label{lem:2}
Every sequence of stones that can be stacked together is a common subsequence
of $S_\ell$ and $S_w$. 
\end{Lemma}
\begin{Proof}
Let $s_1$, $s_2$, \ldots, $s_i$, \ldots, $s_k$ denote a sequence of $k$ stones
that can be stacked together in that order.  That is, $s_i$ can be stacked on
top of $s_{i+1}$ for all $i$ between $1$ and $k-1$.  If two stones have the
same length and height (i.e., they have identical dimensions), then we follow
the same rule as we did in the algorithm to decide which stone we place ahead
in the sequence.  Both the lengths as well as the widths of the sequence are
in nondecreasing order.  Therefore, the sequence is a subsequence of both
$S_\ell$ and $S_w$.
\end{Proof}

It follows from Lemma~\ref{lem:1} and~\ref{lem:2} that the longest sequence of
``stackable'' stones is the longest common subsequence of $S_\ell$ and $S_w$.

\item {\bf Algorithm~2:} In this solution, we first sort all the stones
according to their lengths in nondecreasing order, breaking ties according to
their widths.  In this solution, we assume that no two stones are identical.
We can do away with this assumption using a trick similar to the one we used
in the previous solution.  Let the list of stones thus obtained be $S = s_1,
s_2, \ldots, s_n$.  It thus follows that if $i > j$, then $s_i$ cannot be
stacked on top of $s_j$.  We now can give a simple recurrence relation to
compute $C[i]$, the maximum number of stones that can be stacked together with
stone $s_i$ being at the bottom.
\[
C[i] = \max\left\{1, \max\{C[j] + 1: j < i \mbox{ and } j \mbox{ can be stacked on top of } i\}\right\}.
\]
The correctness of the recurrence relation can be proved by induction on $i$.
The induction basis is trivial.  For the induction step, we note that if the
optimal stacking of stones on top of $s_i$ consists of stacking $s_j$ on $s_i$
and then stacking a sequence $\sigma$ of stones on $s_j$, then the sequence
$\sigma$ together with $s_j$ yields an optimal stacking of stones on top of
$s_j$.  Since $j < i$, we have by the induction hypothesis that $C[j]$ equals
the cost of $\sigma$.  Since the recurrence relation guarantees that $C[i]$ is
at least $C[j] + 1$, we obtain that $C[i]$ yields the number of stones in the
optimal stacking with stone $s_i$ being at the bottom.

The algorithm for finding the number of stones in the optimal stacking, we
calculate $C[i]$ for all $i$ going from $1$ to $n$, i.e., according to the
order in $S$.  Then we return the maximum of $C[i]$ over all $i$ between $1$
and $n$.  The running time is $\Theta(n^2)$ since the calculation of $C[i]$
takes $O(i)$ time.
\end{itemize}

\end{document}
