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

\head{3390}{Analysis of Algorithms}{18 November 1998}{20}

\begin{center}
\Large{\bf Problem of the Week -- 8}
\end{center}

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 the algorithm and analyze its running
time.

({\em Remark:} Observe the similarity to POW--7.  While a solution to the
present problem can be obtained along the same lines as for POW--7 using
dynamic programming, you are asked to design a much more efficient algorithm
using a greedy strategy.)

\end{document}