Make your own free website on Tripod.com

Assignment #3

 

Exercise 16.1.1:

Give a dynamic programming algorithm for the activity selection problem, based on recurrence (16.3). Have your algorithm compute the size c[i,j] as defined above and also produce the maximum-size subset A of activities. Assume that the inputs have been sorted as in equation (16.1). Compare the running time of your solution to the running time of GREEDY-ACTIVITY-SELECTOR.

Answer:

GREEDY-ACTIVITY-SELECTOR(s,f,i,j) /* Main procedure */

m ß   i + 1

while m < j and sm < fj  /* Loop through all activities */

  do m ß m + 1

  if m < j

 

/* Calculation and call a RECURSIVE sub function */

 then return {am} U RECURSIVE-ACTIVITY-SELECTOR(s,f,i,j)

 else

 return end

 

 

/* RECURSIVE sub function */

RECURSIVE-ACTIVITY-SELECTOR(s,f,i,j)

(to be continued…)

 

Exercise 16.1.2:

Suppose that instead of always selecting the first activity to finish, we select the last activity to start that is compatible with all previously selected activities. Describe how this approach is greedy algorithm, and prove that yields an optimal solution.

Answer:

Given theorem 16.1:

Consider any nonempty subproblem Si j and let am be the activity in Si j with the earliest finish time:

            fm = min {fk : ak Î Si j }.

Then

  1. Activity am is used in some maximum-size subset of mutually compatible activity of Si j
  2. The subproblem Si m is empty, so that choosing am leaves the subproblem Sm j as the only one may be nonempty.

A Greedy algorithm always makes the choice look best at that moment. It makes the choice and hopes it will lead to the globally optimal solution, as one subproblem will be empty and the optimal solution will be exist in the nonempty subproblem. Therefore regardless of where you select for the starting point that will compatible with all previously selected activities.

Prove: To prove that am is used in some maximum-size subset of mutually compatible activities of Si j. We suppose that Ai j is the maximum-size subset of mutually compatible activities of Si j, also arrange the activities in order of Ai j in monotonically decreasing order of start time. Let ak be the last activity in the Ai j.

If ak = am then we do not need to go any further because am is equal with ak that means am is used in the maximum-size subset of mutually compatible activities of Si j.

If ak ¹ am then we build the subset A’i j = Ai j – {ak} U {am}. The activities in A’i j are disjoint, since the activities in Ai j are, ak is the last activity in Ai j to start, and sm £ sk. Noting that A’i j has the same number of activities as Ai j. That proves A’i j is the maximum-size subset of mutually compatible activities of Si j that includes am.

 

 


 

 

 

 Here is a set of activities, which are sorted in monotonically decreasing of start time.

 

i

11

10

9

8

7

6

5

4

3

2

1

Si

12

2

8

8

6

5

3

5

0

3

1

fi

14

13

12

11

10

9

8

7

6

5

4

 

Figure 1:

In Figure 1 shows that am is used in the maximum-size subset of mutually compatible of activities (shows in all the green boxes). That makes a greed choice of the activity-selector problem, the activities a11, a10, a6 and a4 all has the starting time greater or equal to the finish time of the previous activity. That constructs the biggest mutually compatible of activities

 

 

Exercise 16.1.3:

Suppose that we have a set of activities to schedule among number of large lecture halls. We wish to schedule all activities using as few lecture halls as possible. Give a efficient greedy algorithm to determine which activity should use which lecture hall.

(This is also known as the interval-graph coloring problem. We can create an interval graph whose the vertices are the given the same color corresponds to the finding the fewest lecture halls needed to the schedule all of the given activities.)

Answer:

We can divide the scheduling problem into subsets each subset represent the best choice for each lecture hall n = 1,2, ….z = number of lecture hall. And supposes that an activity an has a start time si and finish time fi is used in the maximum-size of mutually compatible of activities for each lecture hall. We will show that the greedy algorithm is optimal in the sense that it always schedules the most activities possible for each lecture hall

Step1: We can draw all activities as figure 1 above. Suppose that the greedy algorithm a1 (n = 1) manages schedule for lecture hall # 1 that is used the maximum-size of activities mutually compatible in this case we will have all the “green” boxes such as activities: a11, a10, a6 and a4.

Step2: Our algorithm will search through the remain activities again and construct the greedy algorithm a2 for lecture hall # 2 so that lecture hall # 2 will has a maximum-size of activities mutually compatible. For example: a5, a9 on figure 1 will be scheduled in lecture hall number 2. Loop through the matrix we will have a1, a8 in hall #3, a2, a7 in hall # 4 and a3 will be in hall # 5.

Step3: Combine the optimal results we will use 5 lecture halls for 11 activities