\documentstyle[11pt,handout]{article}
\begin{document}
\input{macros}
\input{/home/rraj/Courses/1390/Syllabus/localmacros}
\newcommand{\hs}{\hspace{1em}}
\newcommand{\Hspace}{\hspace{1em}}

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

\newcommand{\lmis}[1]{\mbox{{\sc LMIS}}[#1]}
\newcommand{\myappend}[1]{\mbox{append}\left(#1\right)}
\newcommand{\emax}{{\sc Extract-Max}}
\newcommand{\ins}{{\sc Insert}}

\head{1390}{Algorithms}{Winter 1999}{9 March 1999}{21}

\begin{center}
\Large{\bf Sample Solution to Problem Set 4}
\end{center}

\bigskip
{\bf 1. (15 points)} Exercise 16.3--5.  

{\bf Answer:} Here are two approaches to the problem.
\begin{enumerate}
\item 
Given that we have already considered the longest common subsequence problem
(LCS) in class (also Section 16.3), there is an easy reduction from the
longest monotically increasing subsequence problem (LMIS) to LCS.  Let $X$ be
the given sequence of $n$ numbers.  Let $Y$ be the set of numbers in $X$
sorted in increasing order, in which we remove any duplicates.  Thus, the
length of $Y$ is at most $n$.  Now we claim that the LMIS of $X$ is the same
as the LCS of $X$ and $Y$.  If the claim holds, then the LMIS of $X$ can be
obtained by running the LCS algorithm which will take $\Theta(n^2)$ time.

The above claim follows from the following two observations: (i) any
monotonically increasing subsequence of $X$ is a common subsequence of $X$ and
$Y$, and (ii) any common subsequence of $X$ and $Y$ is a monotonically
increasing subsequence of $X$.  Therefore, a {\em longest}\/ monotonically
increasing subsequence of $X$ is the same as a {\em longest}\/ common
subsequence of $X$ and $Y$.

\item
An alternative approach is by first principles.  Let $\lmis{i}$ denote the
LMIS of $X$ that ends at $X[i]$.  We now give a recurrence relation for
calculating $\lmis{i}$ as follows:
\[
\lmis{i} =  \left \{
\begin{array}{ll}
	X[i] & \mbox{ if $i = 1$.}\\
	\myappend{\max_{1 \le j < i} \{\lmis{j} : X[j] < X[i]\}, X[i]} & otherwise.
\end{array}
\right.
\]
In the above equation, the ``max'' function returns the set largest in size,
if one exists; otherwise, it returns the empty set.  We justify the above
equation as follows.  If $i = 1$, then clearly the LMIS ending at $X[i]$
trivially consists of $X[i]$ only.  Otherwise, the LMIS ending at $X[i]$ is
equal to $X[i]$ appended to the longest of the LMISs ending at any $X[j]$ that
satisfies $X[j] < X[i]$.

The algorithm consists of simply computing $\lmis{i}$ iteratively, $i$ going
from $1$ to $n$.  Since the computation of any $\lmis{i}$ requires the
computation of the maximum of at most $n$ sets, the running time of the
algorithm is $n \cdot O(n) = O(n^2)$.

{\em Remark:} By using a data structure like a balanced binary search tree, one
can reduce the running time of the algorithm to $O(n \log n)$.
\end{enumerate}

{\bf 2.} 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) (5 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.

{\bf Answer:} 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 (and Section 17.1) 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) (20 points)}]
Use dynamic programming to solve the weighted activity selection problem.
Analyze the running time of your algorithm.

{\bf Answer:} 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 3. (20 points)} Suppose you are a high-level manager in a software firm and you are
managing $n$ software projects.  You are asked to assign $m$ of the
programmers in your firm among these $n$ projects.  Assume that all of the
programmers are equally competent.

After some careful thought, you have figured out how much benefit $i$
programmers will bring to project $j$.  View this benefit as a number.
Formally put, for each project $j$, you have computed an array $A_j[0..m]$
where $A_j[i]$ is the benefit obtained by assigning $i$ programmers to project
$j$.  Assume that $A_j[i]$ is nondecreasing with increasing $i$.  Further make
the economically sound assumption that the marginal benefit obtained by
assigning an $i$th programmer to a project is nonincreasing as $i$ increases.
Thus, for all $j$ and $i \ge 1$, $A_j[i+1] - A_j[i] \le A_j[i] - A_j[i-1]$.

Design a greedy algorithm to determine how many programmers you will assign to
each project such that the total benefit obtained over all projects is
maximized.  Justify the correctness of your algorithm and analyze its running
time.

{\bf Answer:} We assign programmers one at a time, from $1$ to $m$.  At the
$i$th step, we greedily assign the $i$th programmer to the project to which
the programmer will bring the most marginal benefit.  Note that the marginal
benefit that the $i$th programmer brings to a project $j$ depends on the
particular assignment of the previous $i - 1$ programmers; it may not be the
same as $A_j[i]$.

We now prove that the above greedy choice leads to an optimal solution using a
standard ``swapping argument''.  Our main claim is this: for all $i$, the
assignment obtained after the $i$th step is the subset of an optimal
assignment.  We prove the claim by induction. 

The induction basis is trivial since we start with an empty assignment which
is clearly a subset of an optimal assignment.  As the induction hypothesis, we
assume that the claim holds after step $i - 1$.  That is, the assignment
obtained after step $i - 1$ is a subset of an optimal assignment, say $S$.  We
now consider the state after step $i$.  Let us suppose that the greedy choice
assigns the $i$th programmer to project $j$, thus resulting in $k$ programmers
for project $j$.  If $S$ has assigned at least $k$ programmers to project $j$,
then there is nothing to prove.  (Note that by the induction hypothesis, $S$
has assigned at least $k - 1$ programmers to project $j$.)  Consider the case
in which $S$ has assigned only $k - 1$ programmers.  This implies that there
must be some other project $j'$ such that $S$ has assigned more programmers
than the greedy assignment has assigned thus far.  By the definition of our
greedy choice and the assumption about marginal benefits, it follows that if
we modify $S$ by removing one programmer from project $j'$ and move it to $j$,
the change in total benefit cannot decrease.  Therefore, the new assignment
thus obtained by modifying $S$ is optimal.  It also contains the current
greedy assignment, thus establishing the induction step.

We now consider the running time of the greedy algorithm.  We have $m$
iterations and in each iteration we are determining the project for which the
marginal benefit will be maximum.  Thus, a naive $n$-element comparison to
determine the maximum will take $O(n)$ time, leading to a runtime of
$\Theta(nm)$.  One can do better by maintaining a priority queue in which we
store an element for each project, representing the marginal benefit the next
programmer will bring to the project.  Initially, we add $n$ entries to a
priority queue, one for each of the projects, representing the marginal
benefit that the first programmer brings to the project.  As we have seen in
class (and Chapter 7), we can implement this in $O(n)$ time using {\sc
Build-Heap}.  Each iteration then translates to one \emax\ operation (to find
the project to which the programmer will be assigned) and an \ins\ operation
to insert a new element giving the marginal benefit the next programmer will
bring to the chosen project.  Each iteration thus takes $O(\log n)$ time, thus
leading to a total runtime of $O(n + m\log n)$.

{\bf (10 bonus points)} Now {\em remove}\/ the assumption made above that the
marginal benefit obtained by assigning an $i$th programmer to a project is
nonincreasing as $i$ increases.  Design a dynamic programming algorithm to
determine how many programmers you will assign to each project such that the
total benefit obtained over all projects is maximized.  Analyze its running
time.

{\bf Answer:} Let $C[i,j]$ denote the total benefit obtained in the optimal
assignment $i$ programmers among projects $1$ through $j$.  Let $B[i,j]$
denote the number of programmers assigned to the $j$th project in this optimal
solution.  We can establish the following recurrences for $C[i,j]$ and
$B[i,j]$. We set $C[0,j]$ to $0$ for all $j$.  Furthermore, for all $i$,
$C[i,1]$ equals $A_1[i]$ and $B[i,1]$ equals $i$.  For $i > 0$ and $j > 1$, we
have the following.  Let $k$ be such that $A_j[k] + C[i-k,j-1] = \max_{0 \le \ell
\le i} \{A_j[\ell] + C[i-\ell,j-1]\}$.  Then, $C[i,j] = A_j[k] + C[i-k,j-1]$
and $B[i,j] = k$.  

The algorithm proceeds by iteratively computing $C[i,j]$ and $B[i,j]$, $i$
going from $1$ through $m$ and $j$ going from $1$ through $n$.  The final
assignment can be computed using the $B$ array.  In each iteration, we need to
take the maximum of at most $m$ entries.  Therefore, there are at most $nm$
iterations, each taking $O(m)$ time, leading to a runtime of $O(m^2 n)$.

Note that in the above argument, we do not use the property about marginal
benefits that was used in the first part of the problem.  The property that
the array $A_j$ is nondecreasing is implicitly used by the fact that we try
to get as much benefit as we can by using all of our programmers.

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

{\bf Answer:} For the character set $a$, $b$, $c$, $d$, $e$, $f$, $g$, and
$h$, with the frequencies $1$, $1$, $2$, $3$, $5$, $8$, $13$, and $21$,
respectively, the Huffman code is $0000000$, $0000001$, $000001$, $00001$,
$0001$, $001$, $01$, and $1$, respectively.  In general, for an $n$-length
Fibonacci sequence, the Huffman encoding is $n-1$ 0's for $a_1$, and $n-i$ 0's
followed by a $1$ for $a_i$, $2 \le i \le n$.  
\end{document}
