Algorithms Assignment 6: Greedy Algorithms

EECS 340/454: Algorithms
Assignment 6: Greedy Algorithms

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.