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 Aj $[0..$m$]$ where

Aj $[$i$]$ is the benefit obtained by assigning i programmers to project j$.$ Assume that Aj $[$i$]$ is nondecreasing

with increasing i$.$

In this question, you will design a dynamic programming algorithm to determine how many programmers

you will assign to each project so that the total benefit obtained over all projects is maximized.

$($a$)$ Describe the set of subproblems that your dynamic programming algorithm will consider. Your solution

should look something like $$For every $...,$ we define OP T $[...]$ to be $...$

$($b$)$ Give a recurrence expressing the solution to each subproblem in terms of the solution to smaller

subproblems.

$($c$)$ Using your recurrence, design a dynamic programming algorithm to output the optimal allocation of

programmers to the n projects. You may use either a top$-$down or bottom$-$up approach. Remember

that your algorithm needs to output the optimal allocation, not only its benefit. The output of your

algorithm can be an array of length n where the ith entry gives the number of programmers allocated

to project i in the optimal allocation.

$($d$)$ Analyze the running time and space usage of your algorithm.