CS 561, HW4
Prof. Jared Saia, University of New Mexico
Due: October 14th
1. Consider the following alternative greedy algorithms for the activity
selection problem discussed in class. For each algorithm, either prove
...
CS 561, HW4
Prof. Jared Saia, University of New Mexico
Due: October 14th
1. Consider the following alternative greedy algorithms for the activity
selection problem discussed in class. For each algorithm, either prove
or disprove that it constructs an optimal schedule.
• Choose an activity with shortest duration, discard all conflicting
activities and recurse
• Choose an activity that starts first, discard all conflicting activities and recurse
• Choose an activity that ends latest, discard all conflicting activities and recurse
• Choose an activity that conflicts with the fewest other activities,
discard all conflicting activities and recurse
2. Now consider a weighted version of the activity selection problem.
Imagine that each activity, ai has a weight, w(ai) (weights are totally
unrelated to activity duration). Your goal is now to choose a set of nonconicting activities that give you the largest possible sum of weights,
given an array of start times, end times, and values as input.
(a) Prove that the greedy algorithm described in class - Choose the
activity that ends first and recurse - does not always return an
optimal schedule for this problem
(b) Describe an algorithm to compute the optimal schedule in O(n2)
time. Hint: 1) Sort the activities by finish times. 2) Let m(j) be
the maximum weight achievable from activities a1; a2; : : : ; aj. 3)
Come up with a recursive formulation for m(j) and use dynamic
programming. Hint 2: In the recursion in step 3, it’ll help if you
precompute for each job j, the value xj which is the largest index
i less than j such that job i is compatible with job j. Then when
1computing m(j), consider that the optimal schedule could either
[Show More]