Question

show all your work. justify your answer

Exercise 3 (20 points) This exercise is about the greedy approach to the activity-selection problem. James claims that in some cases the elimination of the first activity to finish from the set of activities can lead to a larger set of mutually compatible activities. Is James right or wrong? Prove your answer

Answer 1

Activity selection problem is a problem in which a person has a list of work to do. Each of the activities has a starting time and ending time . We need to schedule all these activities in such a way that the person can complete a maximum number of activities. Since the timing of the activities can collapse, so it might not be possible to complete all activities and thus we need to schedule the activities in sach a way that the maximum number of activities can be finished.

EXAMPLE : Look at the table containing activities with their start and end times.

Activity (a)1 4 6 2 0 2 3 4 3 Si 4 3 6

Here si and fi are the starting and the finishing time of the activity ai.

Activity 1 Activity 2 Activity 3 Activity 4 Activity5 0 3 6

GREEDY APPROACH

We want to adjust the maximum number of activities to be completed . So, choosing the activity which is going to finish first will leave us maximum time to adjust the later activities. This is basically an intuition that greedily choosing the activity with earliest finish time will give us an optimal solution. Thus, our next task is to verify our intuition.

VERIFYING GREEDY APPROACH

Suppose we have adjusted some activities in the given time slot and claiming that this solution is the optimal solution and fhe element first to be finished is not in this solution.

To finish first Scheduled Activities

Now we can replace the first activity in the slot with the element with first finish time without any consequences. As we are only concerned with the number of activites and by replacing the activity , the number of activies will be the same.

Replaced Free Space

This is even going to give us some free time in the slot which can be used to further optimize the problem. So, we need the element of least finish time in our optimal solution and thus we just theoretically verified that making a greedy choice will lead us to optimal solution.

SOLVING THE PROBLEM

Now we kn that greedily choosing the activity with least finish time will give us the optimal solution , so our first task would be to sort the activities with their finishing times.

Activity (ai) 3 4 5 0 4 Si 2 4 6 6 Sorted according to finish time

To take the element with the least finish time , we will iterate over the list of the activities and will select the first activity and then we will select the activity which is starting next after the currently selected activity finishes.

0 2 Took this 3 4 6 Then took this 4 First to start after 2 finishes Activity 1 Activity 2 Activity 5 0 3 6

Hence, we can say that James is right.