 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.

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,f)

else

return end

/* RECURSIVE sub function */

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

(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.

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.)