Suppose that on a busy day of the semester you get homework for each of the n co

Question

Suppose that on a busy day of the semester you get homework for each of the n courses that you are taking. Homework for the ith course is due within ti days, and you earn pi points for submitting the homework on time. Unfortunately it takes you one full day to do each homework. So, for example, if you have 4 homeworks due within 2 , 3 , 1 , and 2 days, respectively, you cannot submit all four on time, but you can submit the first three on time by doing the third one on day 1 , the first one on day 2 , and the second one on day 3 . Your objective is to maximize the total number of points you can earn by submitting a subset of the homeworks on time.

(a) Let S be a subset of all homeworks. Call S “reasonable” if there is an order in which you can do the

homeworks in S so that each one can be submitted on time. Prove that S is reasonable if and only if for all

integers t <= n , the number of homeworks in S due within t days or less is no more than t .

(Hint: Consider doing the homework in increasing order of due date.)

(b) Design a polynomial time greedy algorithm to determine which homework to do on which day so as to

maximize the number of points you can earn by submitting a subset of the homework on time. Prove the

correctness of your algorithm and analyze its running time.

(Hint: Build up a reasonable set of homeworks greedily by considering homeworks in a particular order and

adding each homework to your schedule if the set of selected homeworks continues to remain reasonable.

Use part (a) to check for feasibility. What order should you consider homeworks in to maximize the

number of points earned? Use an exchange argument to prove the correctness of your algorithm.)

Explanation / Answer

(a)

The set of all homeworks S is Called S “reasonable” if there is an order in which you can do the homeworks in S on time. Given that we have n homeworks in S with deadlines [t1 t2 t3 t4 t5 ....... tn] respectively.

We need to show that S is reasonable if and only if for all values of t in the range 1<= t <= n, the number of homeworks in S that are due in less than or equal to t days is less or eqaul to t.

Proof:

So we will prove this by contradiction. Let us assume that there exists a value of t in the range (1 <= t <= n) such that the number of homeworks in S that are due in less than or equal to t days is more than t.

So, it is clear that we have t days and we need to submit more than t homeworks in t days.

But as each homework takes atleast 1 day, we can complete atmost t homeworks in t days. Hence this is the contradiction. Hence our assumption was wrong.

Hence S is reasonable if and only if for all values of t in the range 1<= t <= n, the number of homeworks in S that are due in less than or equal to t days is less or eqaul to t.

(b)

The greedy strategy we will use is "Solve the homework with earliest deadline first ". That is, we should solve that homework first which is having least number of days for its deadline.

Algorithm:

{

if(t[i] <= i)

{

t[i] is submitted on time.   

}

else

{

t[i] is not submitted on time.   

}

}

Proof of correctness by exchange argument:

We are given set of deadlines t = [t1 t2 t3 t4 t5 ....... tn] . We sort t increasingly. And then we solve each of them sequentially if the deadline of each of them is not expired.

Let i and j are deadlines of homeworks, if i <= j,So according to our algorithm, homework i is solve first and then homework j is solved.

According to exchange argument if we solve homework j first and then homework i, it can be proved that this strategy never performs better than our strategy.

Hence Our strategy will always be correct.

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

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