Give a dynamic programming solution for the Activity Selecti

Give a dynamic programming solution for the Activity Selection problem, based on the recurrence

Assume that the inputs are sorted in order of increasing finish time. What is your algorithm’s running time? (Remember to give a correctness proof)

Solution

Dynamic programming solution can be given as

DYNAMICACTIVITYSELECTOR(s , f , n)
let c[0..n+1, 0..n+1] and act[0..n+1, 0..n+1] be new tables

for i = 0 to n c[i,i]=0

c[i, i+1]=0 c[n+1, n+1] = 0

for l = 2 to n+1
for i = 0 to nl+1

j = i+l c[i,j]=0
k = j 1
while f[i] < f[k]

if f[i] <= s[k] and f[k] <= s[j]
and c[i, k] + c[k, j] + 1 > c[i, j] do c[i,j]=c[i,k]+c[k,j]+1
act[i, j]=k

k = k 1
print ”A max size set of mutually compatible activities ” print c[0, n+1]
print ”The set contains ”

PRINTACTIVITIES(c, act, 0, n+1)

PRINTACTIVITIES(c, act, i, j) ifc[i,j]>0

k=act[i, j] print k

PRINTACTIVITIES(c, act, i, k) PRINTACTIVITIES(c, act, k, j)

The PRINT-ACTIVITIES procedure recursively prints the set of activities placed into the optimal solution Aij . It first prints the activity k that achieved the maximum value of C[i,j], and then it recurses to print the activities in Aik and Akj. The recursion bottoms out when c[i,j] = 0, so that Aij = .

Whereas GREEDY-ACTIVITY-SELECTOR runs in (n) time, the DYNAMIC- ACTIVITY -S ELECTOR procedure runs in O(n3) time.