\documentstyle[11pt,handout]{article}
\begin{document}
\input{macros}
\input{localmacros}

\renewcommand{\name}{\mbox{{\em name}}}
\newcommand{\color}{\mbox{{\em color}}}
\newcommand{\myyear}{\mbox{{\em year}}}
\newcommand{\salary}{\mbox{{\em salary}}}
\newcommand{\salarysum}{\mbox{{\em salarysum}}}
\newcommand{\num}{\mbox{{\em num}}}
\newcommand{\prefixnum}{\mbox{{\em prefixnum}}}
\newcommand{\prefixsalarysum}{\mbox{{\em prefixsalarysum}}}
\newcommand{\prefixsalary}{\mbox{{\em prefixsalary}}}
\newcommand{\treenum}{\mbox{{\em treenum}}}
\newcommand{\treesalarysum}{\mbox{{\em treesalarysum}}}
\newcommand{\pointer}{\mbox{{\em pointer}}}

\renewcommand{\cp}{\mbox{{\em copy}}}
\newcommand{\ins}{\mbox{{\em insert}}}
\newcommand{\rep}{\mbox{{\em replace}}}
\newcommand{\del}{\mbox{{\em delete}}}
\newcommand{\twi}{\mbox{{\em twiddle}}}
\newcommand{\kil}{\mbox{{\em kill}}}
\newcommand{\cost}{\mbox{cost}}
\newcommand{\op}{\mbox{{\em op}}}
\newcommand{\Compute}{\mbox{{\sc Compute}}}

\newcommand{\remaining}{\mbox{{\em remaining}}}
\newcommand{\print}{\mbox{{\bf print}}}
\newcommand{\minpair}{\mbox{{\em minpair}}}
\newcommand{\Max}{\mbox{{\em Max}}}

\renewcommand{\insert}{\mbox{{\sc Insert}}}
\newcommand{\exmin}{\mbox{{\sc Extract-Min}}}
\newcommand{\exmax}{\mbox{{\sc Extract-Max}}}
\newcommand{\enq}{\mbox{{\sc Enqueue}}}
\newcommand{\deq}{\mbox{{\sc Dequeue}}}
\newcommand{\sempty}{\mbox{{\sc Stack-Empty}}}
\newcommand{\Nil}{\mbox{{\sc Nil}}}
\newcommand{\pop}{\mbox{{\sc Pop}}}
\newcommand{\push}{\mbox{{\sc Push}}}

\newcommand{\mytrue}{\mbox{{\bf True}}}
\newcommand{\myfalse}{\mbox{{\bf False}}}

\thispagestyle{empty}
\setlength{\parindent}{0pt}
\setlength{\parskip}{1.8ex}

\head{3390}{Analysis of Algorithms}{9 December 1998}{25}

\begin{center}
\Large{\bf Sample Solutions to Problem Set 3}
\end{center}

\bigskip
{\bf Problem~1. (12 points)} Suppose you are maintaining a database that relates the
salaries of the employees in your firm to their ages.  Design a data structure
that efficiently supports the following three operations:
\begin{itemize}
\item
{\sc Insert}$(\name, \myyear, \salary)$, where $\name$ is the name of an
employee, $\myyear$ is the year of birth of the employee and $\salary$ is the
annual salary of the employee.  You should assume that the names of all of the
employees are distinct.

\item
{\sc Delete}$(\name, \myyear)$, where $\name$ is the name of an employee in the
database and $\myyear$ is the year of birth of the employee.

\item
{\sc Average}$(y_1, y_2)$, where $y_1$ and $y_2$ are two years and $y_1 \le
y_2$.  This operation returns the average salary of the employees born between
$y_1$ and $y_2$, both years included.
\end{itemize}
({\em Hint:}\/ Make use of an appropriately-augmented balanced binary search
tree.)

{\bf Answer:} There are several possible solutions to this problem.  In the
following, we briefly describe three approaches:
\begin{itemize}
\item
{\bf First Approach:} We maintain a single red-black tree in which each node
has the following fields in addition to the standard $\myleft$, $\myright$,
$\parent$, and $\color$ fields: $\name$, $\myyear$ (the year of birth),
$\num$, and $\salarysum$.  The field $\num[x]$ is the total number of nodes in
the subtree rooted at $x$ and $\salarysum[x]$ is the sum of the salaries of
the nodes in the subtree rooted at $x$.  The key for a node is the ordered
pair $(\myyear, \name)$.  That is, the key of a node $x$ is less than that of
a node $y$ if and only if either $\myyear[x] < \myyear[y]$ or $\myyear[x] =
\myyear[y]$ and $\name[x] < \name[y]$.

The {\sc Insert} and {\sc Delete} operations are defined as for regular
red-black trees.  However, we need to update the augmented fields $\num$ and
$\salarysum$.  We invoke Theorem~15.1 of text to argue that these fields can
be maintained without increasing the asymptotic complexity of the {\sc Insert}
and {\sc Delete} operations.  For this, we just note that both the fields
$\num[x]$ and $\salarysum[x]$ can be calculated from the other fields of $x$
and the fields of $\myleft[x]$ and $\myright[x]$.  Thus, both {\sc Insert} and
{\sc Delete} take $O(\lg S)$ time, where $S$ is the dynamic set of employees.

For the {\sc Average} operation, we first define two functions $\prefixnum$
and $\prefixsalary$.  For a given year $y$, $\prefixnum(y)$ returns the total
number of employees whose year of birth is less than or equal to $y$, while
$\prefixsalary$ returns the sum of the salaries of employees whose year of
birth is less than or equal to $y$.  It is easy to see that ${\sc
Average}(y_1, y_2)$ equals $(\prefixsalary(y_2) -
\prefixsalary(y_1-1))/(\prefixnum(y_2) - \prefixnum(y_1-1))$.  So all that
remains to be done is to efficiently compute $\prefixnum$ and $\prefixsalary$.

We only define $\prefixnum$ here.  The function $\prefixsalary$ can be
analogously defined.  Given $y$, $\prefixnum(y)$ can be calculated as follows.
We first search for the largest element in $S$ (according to the key) with
year of birth equal to $y$.  During our search, every time we encounter a node
whose year of birth field is equal to $y$, we go to its right child.  Our
search terminates when we reach a leaf ({\sc Nil}) node.  Let $u$ be the
parent of this leaf.  (Thus $u$ is the last internal node reached in the
search.)  We now retrace the path from $u$ up to the root and will finally
return a number $r$ that equals the total number of nodes whose year of birth
is at most $y$.  Initially, we set $r$ to $0$.  We now perform the following
computation which is very similar to the one we studied in the rank
computation and in Problem~5 of the midterm.
\begin{tabbing}
\=1. \= \myif\ $\myyear[u] = y$, then $r \leftarrow \num[u]$;\\
\>2. \> \while\ \= $u \neq$ root\\
\>3. \> \> \myif\ \= $u = \myright[p[u]]$\\
\>4. \> \> \>  $r \leftarrow r + \num[\myleft[p[u]]]$\\
\>5. \> \> $u \leftarrow p[u]$\\
\>6. \> \ret\ $r$
\end{tabbing}
In order to justify the correctness of the operation, we need to primarily
justify line~4, which is executed whenever $u$ is the right child of its
parent.  This implies that all the nodes in the left subtree of $p[u]$ have
year values less than or equal to $y$.  So all of the nodes in the left
subtree need to be counted within $r$.  Moreover, the year of birth of the
node $p[u]$ itself is less than or equal to $y$.  Therefore, the employee
stored at that node should also be counted in $r$.  On the other hand, if $u$
is a left child of $p[u]$, then all the nodes in the right subtree of $p[u]$
as well as the node $p[u]$ have year of birth greater than $y$.  Hence, these
employees are not added to $r$.

The running time is easily seen to be $O(\lg |S|)$ since the red-black tree is
height-balanced.

\item
Second Approach: An approach that is cleaner than the one above is use a
red-black tree of red-black trees!  More precisely, the data structure is the
following.  For each year $y$ (that is the year of birth of some employee), we
maintain a red-black tree -- with key being the $\name$ field -- that contains
records of all the employees that have year of birth $y$.  Let us call these
red-black trees the ``year trees''.  Each node in a year red-black tree
contains the following fields: $\name$ and $\salary$.  Next, we maintain a
red-black tree -- whose key is the $\myyear$ field -- that contains pointers
to the year trees.  We call this tree the ``main tree''.  Each node contains
the following fields: $\myyear$, $\pointer$, $\num$, $\salarysum$, $\treenum$,
and $\treesalarysum$.  The field $\pointer$ points to the associated year tree,
$\num$ and $\salarysum$ are the total number of nodes and total salaries,
respectively, in the year tree pointed to by $\pointer$.  The field
$\treenum[u]$ is the total number of the employees in the year trees located
at all nodes that are in the subtree rooted at $u$.  (Note that the subtree
rooted at $u$ is part of the main tree and is different from $\pointer[u]$.)
Similarly, $\treesalarysum[u]$ is the sum of the salaries of the employees in
the year trees located at all nodes that are in the subtree rooted at $u$.
(Also note that if there are no employees with year of birth $y$, then we will
not have a year tree associated with $y$.)

The operation {\sc Insert}$(\name, \myyear, \salary)$ proceeds as follows.  We
search for $\myyear$ in the main tree.  If we find the relevant node in the main
tree, say $u$, then we insert a node containing $\name$ and $\salary$ into the
year tree pointed to by $\pointer[u]$.  We also increment $\num[u]$ by $1$ and
$\salarysum[u]$ by $\salary$.  If we do not find any node associated with year
$y$, we insert a new node $u$ in the main tree with $\myyear$ field $y$, set
$\num[u]$ to $1$, set $\salarysum[u]$ to $\salary$, and set $\pointer[u]$ to a
new year tree that consists of one node whose $\name$ and $\salary$ fields are
$\name$ and $\salary$.  Since the total number of nodes in both the main tree
and the year tree are both at most $|S|$, searching/inserting into the main
tree as well as inserting into the year tree take $O(\lg |S|)$ time each.  We
also need to update the $\treenum$ and the $\treesalarysum$ fields of some
nodes in the main tree.  We note that since these fields can be computed from
other fields of a node and the fields of its children, Theorem~15.1 states
that these updates do not affect the asymptotic complexity of {\sc Insert}.
Therefore, the running time of {\sc Insert} is $O(\lg |S|)$.

The operation {\sc Delete}$(\name, \myyear)$ is also easy.  We search for the
node with the year field $\myyear$ in the main tree.  If no such node exists,
then there is nothing to do.  Otherwise, let $u$ be the node with the year
field $\myyear$.  We then search for the node in $\pointer[u]$ that has name
$\name$.  If no such node exists, then there is nothing to do.  Otherwise, we
delete the node.  Next, we need to update the $\num$ and $\salarysum$ fields
of $u$.  We decrement $\num[u]$ by $1$ and $\salarysum[u]$ by the salary of
the node deleted.  If $\num[u]$ becomes zero, then we delete $u$ from the main
tree.  Again, since the total number of nodes in both the main tree and the
year tree are both at most $|S|$, searching/inserting into the main tree as
well as inserting into the year tree take $O(\lg |S|)$ time each.  We also
need to update the $\treenum$ and the $\treesalarysum$ fields of some nodes in
the main tree.  We note that since these fields can be computed from other
fields of a node and the fields of its children, Theorem~15.1 states that
these updates do not affect the asymptotic complexity of {\sc Delete}.
Therefore, the running time of {\sc Delete} is $O(\lg |S|)$.

The {\sc Average} operation can be calculated by just considering the main
tree and using the $\treenum$ and $\treesalarysum$ fields.  This done in much
the same way as we did in the previous approach.  That is, we define the
$\prefixnum$ and $\prefixsalary$ operations and then compute then the ${\sc
Average}$.  Please see the description in the first approach and fill in the
details.  The running time of {\sc Average} is also $O(\lg |S|)$.

\item
Third Approach: The above two approaches work efficiently regardless of number
of possible year entries.  That is, we make no assumptions about the mortality
of humans.  If, however, we do assume that the number of possible years of
birth for all employees at a given time is constant, then we can maintain an
array $A$ of red-black trees, one for each possible year.  The entry $A[y]$
contains a pointer to a red-black tree consisting of records of all employees
that have year of birth $y$.  $A[y]$ also contains $\num$, the number of
employees, and $\salarysum$, their total salary in the associated red-black
tree.  We do not need to further augment the individual red-black trees.

The {\sc Insert} operation consists of simply inserting a record into
red-black tree pointed to by $A[y]$, where $y$ is the year of birth of the
employee being inserted.  We also need to increment $\num$ and $\salarysum$
appropriately.  The {\sc Delete} operation can be similarly defined.  Both
{\sc Insert} and {\sc Delete} take $O(\lg |S|)$ time in the worst-case.

The {\sc Average}$(y_1, y_2)$ operation can be computed by dividing the sum of
$\salarysum$ values by the sum of $\num$ values, each sum taken over all
entries in $A[y_1..y_2]$.  This takes time $O(y_2 - y_1)$, which is $O(1)$ if
we assume that the year span is a constant.  

Note that if we use this solution, we need to periodically (once every year)
process the data structure so that we reclaim any space that we may be
devoting to the earliest year for which no records presently exist.  We need
to do this in order to avoid using an unbounded amount of space.  Finally, we
also need to be careful to avoid the Y2K problem!
\end{itemize}
{\bf 2. (15 points)} Problem~16--3.

{\bf Answer:} Given strings $x[1..m]$ and $y[1..n]$, we define two matrices
$C[0..m, 0..n]$ and $O[0..m, 0..n]$.  We first consider all the operations but
the \kil\ operation.  The entry $C[i,j]$ is the optimal cost of transforming
$x[1..i]$ to $y[1..j]$, while $O[i,j]$ is the last operation performed in an
optimal transformation of $x[1..i]$ to $y[1..j]$.  (If $i$ equals $0$, then
$x[1..i]$ is the empty string.)  We can now compute $C[i,j]$ and $O[i,j]$
using the following procedure, which we refer to as $\Compute(i,j)$.
\begin{enumerate}
\item
If $i = 0$ and $i = 0$, then set $C[i,j]$ to $0$ and return $C[i,j]$.
\item
Initialize $C[i,j]$ to $\infty$.
\item
\cp: If $i > 0$ and $j > 0$ then if $x[i] = y[j]$ and $C[i-1,j-1] + \cost(\cp)
< C[i,j]$, then set $C[i,j]$ to $C[i-1,j-1] + \cost(\cp)$ and $O[i,j]$ to \cp.
\item
\ins: If $j > 0$ then if $C[i,j-1] + \cost(\ins) < C[i,j]$, then set $C[i,j]$
to $C[i,j-1] + \cost(\ins)$ and $O[i,j]$ to \ins.
\item
\del: If $i > 0$, then if $C[i-1,j] + \cost(\del) < C[i,j]$, then set $C[i,j]$
to $C[i-1,j] + \cost(\del)$ and $O[i,j]$ to \del.
\item
\rep: If $i > 0$ and $j > 0$, then if $C[i-1,j-1] + \cost(\rep) < C[i,j]$, then
set $C[i,j]$ to $C[i-1,j-1] + \cost(\rep)$ and $O[i,j]$ to \rep.
\item
\twi: If $i > 1$ and $j > 1$, then if $x[i] = y[j-1]$, $x[i-1] = y[j]$, and
$C[i-1,j-1] + \cost(\cp) < C[i,j]$, then set $C[i,j]$ to $C[i-2,j-2] +
\cost(\twi)$ and $O[i,j]$ to \twi.
\item
Return $C[i,j]$.
\end{enumerate}

We now prove the correctness of our computation above.  The proof is by
induction on the ordered pair $(i,j)$.  For the induction basis, we note that
$C[0,0]$ is indeed zero.  For the induction step, we first make the hypothesis
that we have correctly computed $C[i',j']$ for all $(i',j')$ such that either
$i' \le i - 1$ or $j' \le j - 1$.  Consider the computation of $C[i,j]$.  Let
$C^*$ be the optimum cost for transforming $x[1..i]$ to $y[1..j]$ without
using the \kil\ operation, and let \op\ be the last operation in this optimal
transformation.  We prove that $C[i,j]$ equals $C^*$ by considering different
cases depending on the operation \op.  Here we only prove for the cases \op =
\cp\ and \op = \twi.  Similar proofs can be given for all other operations
save \kil.

If \op\ is \cp, then the optimal solution would have first
transformed $x[1..i-1]$ to $y[1..j-1]$ and then performed the \cp\ operation.
Therefore, we have $x[i] = y[j]$ and $C^* \ge C[i-1,j-1] + \cost(\cp)$ since
the induction hypothesis says that $C[i-1, j-1]$ is the optimal cost of
transforming $x[1..i-1]$ to $y[1..j-1]$.  In the computation of $C[i,j]$,
step~3 guarantees that $C[i,j] \le C[i-1, j-1] + \cost(\cp) \le C^*$.  Thus,
$C[i,j]$ is indeed the cost of an optimal transformation from $x[1..i]$ to
$y[1..j]$. 

If \op\ is \twi, then the optimal solution would have first transformed
$x[1..i-2]$ to $y[1..j-2]$ and then performed the \twi\ operation.  Therefore,
we have $x[i] = y[j-1]$, $x[i-1] = y[j]$ and $C^* \ge C[i-2,j-2] +
\cost(\twi)$ since the induction hypothesis says that $C[i-2, j-2]$ is the
optimal cost of transforming $x[1..i-2]$ to $y[1..j-2]$.  In the computation
of $C[i,j]$, step~7 guarantees that $C[i,j] \le C[i-2, j-2] + \cost(\twi) \le
C^*$.  Thus, $C[i,j]$ is indeed the cost of an optimal transformation from
$x[1..i]$ to $y[1..j]$.

So our algorithm for computing the optimal costs for transformations not
using the \kil\ operation is the following:
\begin{tabbing}
\=1. \= \for\ \= $i \leftarrow 0$ to $m$\\
\>2. \> \> \for\ \= $j \leftarrow 0$ to $n$\\
\>3. \> \> \> $\Compute(i,j)$
\end{tabbing}

After running the above algorithm, we consider the \kil\ operation by running
the following algorithm:
\begin{itemize}
\item
for $i$ from $1$ to $n$, if $C[i,n] + \cost(\kil) < C[m,n]$, then set $C[m,n]$
to $C[i,n] + \cost(\kil)$ and $O[m,n]$ to ``\kil\ from $i$ onwards''.
\end{itemize}
To prove the optimality of $C[m,n]$, we note that an optimal transformation of
$x[1..m]$ to $y[1..n]$ that ends with a ``\kil\ from $i$ onwards'' consists of
an optimal transformation of $x[1..i]$ to $y[1..n]$ followed by the ``\kil\
from $i$ onwards'' operation.  Since we consider all possible values of $i$ in
the above algorithm and pick the best one, the optimality of $C[m,n]$ holds.

In order to print the optimal transformation, we retrace the computation using
the operation matrix $O$ that we have computed.  We run {\sc Print}$(m,n)$
using the following recursive algorithm:
\begin{tabbing}
{\sc Print}(i, j)\\
\=1. \= \myif\ $i = 0$ and $j = 0$ then \ret\\
\>2. \> \myif\ $O[i,j]$ is \cp\ or \rep\ then {\sc Print}$(i-1, j-1)$\\
\>3. \> \myif\ $O[i,j]$ is \ins\ then {\sc Print}$(i, j-1)$\\
\>4. \> \myif\ $O[i,j]$ is \del\ then {\sc Print}$(i-1, j)$\\
\>5. \> \myif\ $O[i,j]$ is \twi\ then {\sc Print}$(i-2, j-2)$\\
\>5. \> \myif\ $O[i,j]$ is ``\kil\ at $k$'' then {\sc Print}$(k, j)$\\
\>6. \> \print\ $O[i,j]$
\end{tabbing}

{\bf 3. (15 points)} 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}

{\bf 4. (8 + 8 + 4 = 20 points)} Problem~17--1.

{\bf Answer:} 
\begin{Enumerate}
\item[{\bf (a) and (b)}] The greedy algorithm is the following.  
\begin{tabbing}
\=1. $\remaining \leftarrow n$; $S \leftarrow \emptyset$\\
\>2. \while\ $\remaining \neq 0$ do\\
\>3. \= Let $c$ be the largest coin less than or equal to $n$\\
\>4. \> Add $c$ to $S$\\
\>5. $\remaining \leftarrow \remaining - c$
\end{tabbing}
We note step~3 is always defined since $1$ is one of the denominations.  

(In part~(a), for example, if the our solution consists of $m_1$ quarters,
$m_2$ dimes, and $m_3$ pennies, it can be easily seen that $m_1 = \lfloor n/25
\rfloor$, $m_2 = \lfloor (n - 25m_1)/10 \rfloor$, and $m_3 = n - 25m_1 -
10m_2$.)

We prove the coorectness of the greedy algorithm by establishing the optimal
substructure property and the greedy choice property. 

{\noindent {\bf Optimal substructure property:}} Here we need to prove that if
$S$ is an optimal solution for making change for $n$ cents and $c$ be any coin
in $S$, then $S - \{c\}$ is an optimal solution for making change for $n - c$
cents.  The proof is by contradiction.  Let $S'$ be an optimal solution for $n
- c$ cents.  Thus, $S' + \{c\}$ is a valid solution for $n$ cents.  If $S -
\{c\}$ is not an optimal solution for $n - c$ cents, then the number of coins
in $S - \{c\}$ is at least one more than that in $S'$.  This implies $S' +
\{c\}$ has fewer coins than $S$, hence contradicting the fact that $S$ is an
optimal solution for $n$ cents.  (Note that this proof holds no matter what
the coin denominations are.)

{\noindent {\bf Greedy choice property:}} Here we need to prove that if $c$ is
the largest coin denomination less than or equal to $n$, then there exists an
optimal solution for $n$ that contains a $c$ coin.  The proof proceeds as
follows.  Let $S$ be any optimal solution for making change for $n$ cents.  If
$S$ contains a $c$ coin, then there is nothing left to proof.  If not, then
let $S'$ be the smallest subset of coins in $S$ (smallest in terms of the
total value of the coins) that add up to at least $c$.  Since $n \ge c$, $S$
itself is a candidate for $S'$; therefore, $S'$ exists.  By our assumption,
$S'$ does not have $c$.  Let $c'$ be the smallest coin denomination in $S'$.
We have $c' < c$.  Let the total value of $S'$ be $n'$.  Then, it follows that
$n' - c'$, which is the total value of $S' - \{c'\}$, is less than $c$.  This
is because otherwise $S' - \{c'\}$ is a subset of $S$ whose coins add up to at
least $c$, thus contradicting the assumption that $S$ is the smallest such
set.  We thus have $n' \ge c$ and $n' - c' < c$

We first consider the case in which all coins larger than $c'$ are a multiple
of $c'$.  In this case, $n'$ is a multiple of $c'$.  Since $c \le n' < c +
c'$, the only multiple of $c'$ that lies in $[c, c + c')$ is $c$.  Therefore,
$n'$ equals $c$.  We can now replace the set $S'$ in the solution $S$ by a
single coin of denomination $c$ and obtain a solution for $n$ that has no more
coins than $S$.  Thus, the desired claim holds.

The above argument takes care of part~(b) since it is true for each coin $c^i$
that the coins bigger than $c''i$ are all multiple of $c^i$.

The above argument also takes care of the situation when $c'$ equals $1$ or
$5$ for part~(a).  The only case that remains is when $c'$ equals $10$.  In
this case, $c$ has to be $25$, since $c > c'$.  If $c'$ equals $10$, then $25
\le n' < 35$.  Since $n'$ in this case is a multiple of $10$, the only
possibility for $S'$ is $3$ dimes, which we can replace by a quarter and a
nickel and contradict the fact that $S$ was on optimal solution for $n$ cents.

The optimality of the greedy algorithm can now be shown by induction on $n$.
The base case, $n = 0$, is trivial.  For the induction hypothesis, we assume
that the greedy algorithm is optimal for $n < m$.  We now consider the case $n
= m$.  The greedy algorithm proceeds by picking the largest coin less than or
equal to $m$ and adding it to the solution for $m - c$.  By the greedy choice
property, there exists an optimal solution for $m$ that contains $c$.  Let us
say this solution has $x$ coins.  By the optimal substructure property, the
number of coins in the optimal solution for $m - c$ is $x - 1$.  Since the
greedy algorithm obtains the optimal solution for $m - c$ (by the induction
hypothesis), it follows that the number of coins in the solution returned by
the greedy algorithm equals $1$ more than the number of coins in the optimal
solution for $m - c$, i.e. $1 + x - 1 = x$.  This completes the proof.

\item[(c)] A set of coin denominations for which the greedy algorithm does not
yield an optimal solution is pennies, dimes, and quarters.  While making
change for $30$ cents, the greedy algorithm will yield $1$ quarter and $5$
pennies, that is, a total of $6$ coins.  The optimal solution, however, is
$3$ dimes. 
\end{Enumerate}

{\bf 5. (16 points total)} Consider a weighted version of the activity
selection problem, in which each activity has a {\em weight}, in addition to
the start and finish times.  (For example, the weight may signify the
importance of the activity.)  The goal is to select a maximum-weight set of
mutually compatible activities, where the weight of a set of activities is the
sum of the weights of the activities in the set.
\begin{Itemize}
\item[{\bf (a) (4 points)}]
Give a counterexample to show that the greedy choice made for the activity
selection problem will not work for the weighed activity selection problem.

\item[{\bf (b) (12 points)}]
Use dynamic programming to solve the weighted activity selection problem.
Analyze the running time of your algorithm.
\end{Itemize}

{\bf Answer:}
\begin{Itemize}
\item[{\bf (a)}] Consider two activities, the first with start time $1$,
finish time $3$ and weight $1$, and the second with start time $2$, finish
time $4$, and weight $2$.  The greedy algorithm studied in class will yield
the first activity as the solution, while the optimal solution is the second
activity since it has a larger weight than the first one.

\item[{\bf (b)}] We first sort all the activities according to their finish
times.  If two activities have the same finish times, we break ties
arbitrarily.  Let the sorted set of activites be $S$ and the activities in $S$
be numbered $1$ through $n$ in the sorted order.  Thus, if $i > j$, we have
$f_i \ge f_j$. 

For any $i$ in $1$ through $n$, we now give a recurrence relation for $S[i]$,
a maximum-weight set of mutually compatible activities with $i$ as the last
activity to finish.  
\[
S[i]  =  \max\left\{\{i\}, \max\{S[j] \cup \{i\} : j < i \mbox{ and } i \mbox{ is
compatible with } j\}\right\},
\]
where the maximum is taken over the total weight of the sets.  (Note the
similarity to Problem~3.)

We prove the correctness of the above recurrence relation by induction on $i$.
For $i$ equal to $1$, the proof is trivial.  Consider $i > 1$.  Let $S^*$ be
any set of mutually compatible activities with $i$ as the last activity to
finish.  Let $j$ be the activity with the largest finish time in $S^*
\setminus \{i\}$.  (If no such $j$ exists, then $S^* = \{i\}$ and has weight
at most the weight of $S[i]$ since $S[i]$ includes $i$.) Since $i$ is the last
activity to finish in $S^*$, we have $j < i$.  Therefore, by the induction
hypothesis, the weight of $S^* \setminus \{i\}$ is at most the weight of
$S[j]$.  Since $j$ is compatible with $i$, the recurrence relation guarantees
that the weight of $S[i]$ is at least the weight of $S[j]$ plus the weight of
$i$, which is at least the weight of $S^*$.  Therefore, $S[i]$ is a
maximum-weight set of mutually compatible activities with $i$ as the last
activity to finish.

So the algorithm computes $S[i]$ for all $i$ going from $1$ to $n$.  We then
return the maximum-weight set among these $n$ sets.  The running time of the
algorithm is $O(n^2)$ since the calculation of $S[i]$ takes $O(i)$ time ($i$
compatibility checks and then finding the maximum over a set of $i$ elements).
\end{Itemize}

{\bf 6. (10 points)} Exercise~17.3--4.

{\bf Answer:} Let $C$ be a given character set.  For a character $x$ in $C$
let $f[x]$ denote the frequency of $x$.  Let $T$ be the tree corresponding to
the optimal code for $C$.  Then, the length of the codeword for $x$ is its
depth $d_T(x)$ in $T$.  And the cost of the code is $B(T) = \sum_{x \in C}
f[x]d_T(x)$.  We need to show that if the characters are ordered so that their
frequencies are nonincreasing, then their codeword lengths are nondecreasing. 

The proof is by contradiction.  Let, if possible, $x$ and $y$ be two
characters such that $f[x] > f[y]$ and $d_T(x) > d_T(y)$.  If so, then we
could swap the two leaves $x$ and $y$ in $T$ to obtain a new tree $T'$.  We
then have:
\begin{eqnarray*}
B(T')
& = & B(T) - f[x] d_T(x) - f[y] d_T(y) + f[x] d_T(y) + f[y] d_T(x)\\
& = & B(T) + f[x](d_T(y) - d_T(x)) - f[y](d_T(y) - d_T(x))\\
& = & B(T) + (f[x] - f[y])(d_T(y) - d_T(x))\\
& < & B(T),
\end{eqnarray*}
where the last step holds since $f[x] - f[y]$ is positive while $d_T(y) -
d_T(x)$ is negative.  We thus have a contradiction since $T$ was assumed to be
an optimal code.

{\bf 7. (6 + 6 = 12 points)} Exercise~7.5--3.

{\bf Answer:} Whenever we add a record $x$ to our dynamic set $S$, we augment
$x$ by a field, which we call its {\em sequence number}.  Let $s[x]$ denote the
sequence number of $x$.  We also maintain a variable $\Max$ that stores the
largest sequence number assigned thus far.

We represent a first-in first-out queue or a stack by a priority queue in
where the key is the sequence number.
\begin{itemize}
\item First-in first-out queue: We use a priority queue that provides the
\insert\ and \exmin\ operations.  We assume that if $S$ is empty then \exmin\
returns \Nil.  The operations \enq\ and \deq\ for a FIFO queue $Q$ are defined
as follows:
\begin{tabbing}
\= \enq($Q$, $x$)\\
\> 1. \= $\Max \leftarrow \Max + 1$ \\
\> 2. \> $s[x] \leftarrow \Max$\\
\> 3. \> \insert($S$, $x$)\\
\end{tabbing}

\begin{tabbing}
\= \deq($Q$, $x$)\\
\> 1. \= $x \leftarrow \exmin(S)$\\
\> 2. \> \myif\ \= $x = \Nil$\\
\> 3. \> \> \ret\ \Nil\\
\> 4. \> \myelse\ \ret\ $x$
\end{tabbing}

For the correctness of these operations, we need to prove that if an item $x$
is enqueued after item $y$, then $x$ is dequeued after $y$.  If $x$ is
enqueued after $y$, then since the sequence number always increases, the key
of $x$ is greater than the key of $y$.  When $x$ is enqueued, we have two
cases.  If $y$ has already been dequeued, then there is nothing to prove.
Otherwise, both $x$ and $y$ are in the priority queue.  Since the key of $x$
is greater than the key of $y$ and the dequeueing operation always extracts
the item with the minimum key, it follows that $y$ is dequeued before $x$.

\item Stack:  We will use a priority queue that provides the \insert\ and
\exmax\ operations.  We assume that if $S$ is empty then \exmax\
returns \Nil.  The operation \push\ is exactly the same as \enq\ above.  The
operation \pop\ is exactly the same as \deq\ above with \exmin\ replaced by
\exmax.  The correctness of these operations follows in a manner analogous to
the correctness of the first-in-first-out queue operations given above. 

The operation \sempty\ can be defined as follows:
\begin{tabbing}
\= \sempty($T$, $x$)\\
\> 1. \myif\ $\exmax(S) = \Nil$, then \ret\ \mytrue\\
\> 2. \myelse\  \= \ret\ \myfalse.
\end{tabbing}
\end{itemize}

\end{document}


