Assigned:
Wed 07 Oct 2009
Due:
Wed 14 Oct 2009
Problem | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | ... |
---|---|---|---|---|---|---|---|---|---|---|
Credit | RC | RC | RC | EC | RC | RC | NA | RC | RC | ... |
where "RC" is "regular credit", "EC" is "extra credit", and "NA" is "not applicable" (not attempted). Failure to do so will result in an arbitrary set of problems being graded for regular credit, no problems being graded for extra credit, and a five percent penalty assessment.
Required: Do all four of the five problems below. Problem 1 is an exercise in the book but counts as a problem here.
Points: 20 points per problem.
Unless otherwise indicated, exercises and problems are from Introduction to Algorithms by Cormen, Leiserson, Rivest, and Stein. The edition (2^{nd} or 3^{rd}) will be indicated if the numbering differs.
After some careful thought, Nubert has figured out how much benefit i programmers will bring to project j. View this benefit as a number. Formally put, for each project j, he has 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-seemingly-sound assumption that the marginal benefit obtained by assigning an ith programmer to a project is nonincreasing as i increases. Thus, for all j and i ≥ 1, A_{j}[i+1] - A_{j}[i] ≤ A_{j}[i] - A_{j}[i-1].
Help Nubert design a greedy algorithm to determine how many programmers to 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.