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

\head{3390}{Analysis of Algorithms}{Winter 2000}{22 February 2000}{13}

\begin{center}
\Large{\bf Problem Set 3 (due March 7) -- no late homework}
\end{center}

\bigskip 

{\bf 1. (20 points)} Problem 16--1, page 324.

{\bf 2. (15 points)} Let the multi-LCS problem be defined as follows.
The input is a set of $m$ length-$n$ sequences $X_i$, $0 \le i < m$.
The output is a longest sequence $Y$ such that $Y$ is a subsequence of
every $X_i$.  Use dynamic programming to develop an algorithm for the
multi-LCS problem that runs in polynomial time for any fixed constant
$m$.

{\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 (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 4. (10 points)} Exercise~17.3-2, page 344.

{\bf 5. (15 points)} Exercise~23.3-10, page 485.

{\bf 6. (15 points)} Exercise~23.4-5, page 488.

{\bf 7. (15 points)} Prove that if $T_1$ and $T_2$ are two minumum
spanning trees of a graph $G$, then $T_1$ and $T_2$ have the same
``weight distribution'' (i.e., for any weight $w$, both $T_1$ and
$T_2$ contain the same number of edges with weight $w$).

{\bf 8. (7 + 8 + 5 = 20 points)} Problem~18--1, page 375.

{\bf 9. (5 + 3 + 12 = 20 points)} Problem~25--2, page 546.
\end{document}

