Suppose you are given a set S = {a1,a2,.,an} of tasks, where task a; requires pi...

 

Transcribed Image Text:

Suppose you are given a set S = {a1,a2,.,an} of tasks, where task a; requires pi units of processing time to complete, once it has started. You have one computer on which to run these tasks, and the computer can run only one task at a time. Let c; be the completion time of task a;, that is, the time at which task a; completes processing. Your goal is to minimize the average completion time, that is, to minimize E1 Ci. For example, suppose there are two tasks, aj and az, with pi = 3 and p2 = 5, and consider the schedule in which az runs first, followed by a1. Then c2 = 5, cl = 8, and the average completion time is (5+8)/236.5. If task aj runs first, however, then c1 = 3, c2 = 8, and the average completion time is (3+8)/2 = 5.5. (1) Design an algorithm that schedules the tasks in S so as to minimize the average completion time. Write down the pseudocode of your algorithm, which should return the minimum average completion time at the end. (2) Compute the time complexity of your algorithm. (3) Prove that your algorithm indeed minimizes the average completion time. Suppose you are given a set S = {a1,a2,.,an} of tasks, where task a; requires pi units of processing time to complete, once it has started. You have one computer on which to run these tasks, and the computer can run only one task at a time. Let c; be the completion time of task a;, that is, the time at which task a; completes processing. Your goal is to minimize the average completion time, that is, to minimize E1 Ci. For example, suppose there are two tasks, aj and az, with pi = 3 and p2 = 5, and consider the schedule in which az runs first, followed by a1. Then c2 = 5, cl = 8, and the average completion time is (5+8)/236.5. If task aj runs first, however, then c1 = 3, c2 = 8, and the average completion time is (3+8)/2 = 5.5. (1) Design an algorithm that schedules the tasks in S so as to minimize the average completion time. Write down the pseudocode of your algorithm, which should return the minimum average completion time at the end. (2) Compute the time complexity of your algorithm. (3) Prove that your algorithm indeed minimizes the average completion time.

Answer rating: 100% (QA)

1 Algorithm is very simple Just we have to observe the thing that scheduling that with less completion time before scheduling task having greater comp... View the full answer