Problem 1
Prove that the following greedy choices do not lead to optimal solutions for the activity selection problem:
(a) Select the activity with the earliest starting time.
(b) Select the activity with least duration.
(c) Select the activity that overlaps the fewest other remaining activities.
Problem 2
We have n activities. Each activity requires ti time to complete and has deadline di. We would like to schedule the activities to minimize the maximum delay in completing any activity; that is,
we would like to assign starting times si to all activities so that max1≤i≤n{∆i} is minimized, where ∆i = fi −di is the delay for activity i and fi = si +ti is the finishing time for activity i. Note that we can only perform one activity at a given time (if activity i starts at time si, the next scheduled activity has to start at time fi).
For example, if t =< 10,5,6,2 and d =< 11,6,12,20 , then the optimal solution is to schedule the activities in the order < 2,1,3,4 to obtain starting/finishing times s/f =< 5/15,0/5,15/21,21/23 and achieve a maximum delay of 9 (for the third activity). State and prove the greedy choice property for this problem.
Problem 3
We have infinite supply of integer coin denominations of c1 = 1 < c2 < ... < ck to make change for a given an integer amount n. For this purpose, we would like to find the minimum number of coins that add up to n. An obvious greedy choice for this problem is to use the largest coin that has value less than or equal to n (e.g., if ck ≤ n, then return ck, and solve the problem for n − ck).
(a) Prove that, if the coin denominations are arbitrary, this greedy choice is not guaranteed to lead to an optimal solution.
(b) Prove that, if the coin denominations are powers of 2, i.e., ci = 2i−1 for 1 ≤ i ≤ k, then this greedy choice is guaranteed to lead to an optimal solution.
