Let S = {a , a , a , …, a } Let S-a1, a2, . . , alo be a set with n-10 activitie

Question

Let S = {a , a , a , …, a }

Let S-a1, a2, . . , alo be a set with n-10 activities. The start time and the finish time of each activity is shown in the table below. Apply the GREEDY-ACTIVITY- SELECTOR function learned in class. What is the subset of activities returned? Write the activities in the correct order in which they are selected by the algorithm. S f a1 5 11 a2 915 15 |13 a4 8 10 a8 27 ag 11 14 Hint: Read carefully the "Note" after the GREEDY-ACTIVITY-SELECTOR function in Module 8.3 pdf "f they (the activities) are not sorted, then we have to sort them irs

Explanation / Answer

Greedy Activity Selection Problem

Algorithm:

Step1 : Sort the activities based on their finish time.

After sorting order of activities becomes:

Table1

Step 2: Select first activity from table created in step 1 and add it to subset of activities to be returned.

Subset becomes : { a6}

Step 3: Select the next activity from the sorted table whose starting time is greater than equal to previous selected activity's finish time.

Note :Selection of activity has to be done in sequence from table1

Repeat step 3 untill all activity has been explored.

So, after a6 , next activity selected is : a10 as it's starting time >= a6 finish time.

Subset becomes : {a6 ,a10 }

Next activity selected : a7

After a7 next activity selected is : a4 as starting time of a4 >= finish time of a7

After a4 next activity selected : a9 as starting time of a9 >= finish time of a4

So, subset of selected activities becomes : {a6 ,a10 ,a7 ,a4 ,a9 }

a6 a10 a8 a7 a5 a4 a1 a3 a9 a2 si 1 4 2 6 7 8 5 5 11 9 fi 3 6 7 8 9 10 11 13 14 15

Related Questions

Navigate

• Browse (All)
• Browse L
• Subjects

---

---

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