2. (20pts) Consider the following variation of Activity Selection problem: Input

Question

2. (20pts) Consider the following variation of Activity Selection problem: Input: A set of n task a1, a2,.., an each expressed as ai-(ri di) where r is the release time, and di the time duration. All the tasks are executed by a single CPU without a time overlap after the time ri taking duration time di Output: Minimum finish time of the last executed task The difference from the original problem is ai- (release time, duration) changed from (start time, finish time): Each task a, is released at the time r, after which the CPU can execute it anytime taking duration di. So the CPU can finish all the tasks anyway. Now you don't maximize the number of executed tasks, but find a schedule with the earliest time to finish all. Design a greedy algorithm running in 0(n2) time to compute the problem. Write all of: o your basic method in 3-10 lines, o complete pseudo code, o proof of the algorithm correctness, and o that of the running time.

Explanation / Answer

int activitySelection(list task){ //return the earliest time to complete all the task

int earliestFinishTime = 0;

sortedListOfTask <- Sort the task on the basis of release time. // it will take n*log(n) time

for (int i=0; i< sortedListOfTask.size() ; i++ ){ // it will loop for n times

t <- sortedListOfTask[i] //get the task having minimum release time and has not been executed yet.

// It will take O(1) time

earliestFinishTime = earliestFinishTime + t.duration ; //execute task t .It will take O(1) time

}

return earliestFinishTime;

}

Correctness:

Here there is no bound on the order of execution of task.So take the task which comes earliest ,execute it then take another task which has not been executed and its release time is earliest ,execute it and so on.

So the CPU does not have to wait for any task at any point of time if atleast one task is available.So finally it willl give the minimum earliest time taken by the CPU to execute all the task.

Running Time:

Sorting will take O(n*log(n)).

loop will iterate for n times and each iteration will take constant time.

So overall complexity is O( n*log(n) )

Related Questions

Navigate

• Browse (All)
• Browse 2
• Subjects

---

---

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