Homework grade maximization: In a class, there are n assignments. You have H hou

Question

Homework grade maximization: In a class, there are n assignments. You have H hours to spend on all assignments, and you cannot divide an hour between assignments, but must spend each hour entirely on a single assignment. The I’th hour you spend on assignment J will improve your grade on assignment J by B[I, J], where for each J, B[1, J] ? B[2, J] ? ... ? B[H, J] ? 0. In other words, if you spend h hours on assignment i=h J, your grade will be i=1 B[i, J] and time spent on each project has diminishing returns, the next hour being worth less than the previous one. You want to divide your H hours between the assignments to maximize your total grade on all the assignments. Give an efficient algorithm for this problem.

Explanation / Answer

I am going to explain an efficient approach to solve the above problem :

Approach :

To figure out how best to divide up the time, we will come up with a set of functions [fi : i = 1, 2, · · · , n] for each of the assignments: if we spend h ? H hours on the assignment i, then you’ll get a grade of fi(h).

We will assume that the functions are non-decreasing (i.e  The algorif h < h0 , then fi(h) ? fi(h 0 )).

With these functions, we will decide how many hours to spend on each assignment.

Algorithm :

Suppose we have a matrix A which is n×H. In other words, each entry A[i, h] represents the maximum grade for taking i assignments and spending h hours on the assignmets total.

We can first observe that A[0, h] = 0 for h = 0, · · · , H and A[i, 0] = P i j=1 fj (0).

We can fill in the rest of the matrix entries by finding k such that:

A[i, h] = max 0?k?h (A[i ? 1, h ? k] + fi(k)). This is a Dynamic Programming relation.

We will keep track of each of the k that we select. It is important to note that with such a way of computing the grades, the final grade that we will receive is the entry A[n, H].

Using the recorded k values, we can back-trace and see how many hours we spent for each assignment. The total time to fill each entry is O(H) and there are nH entries. Thus, we have a total running time of O(nH^2 ).

Related Questions

Navigate

• Browse (All)
• Browse H
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.