Tell me more ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.
up vote 1 down vote favorite

I'm trying to write pseudocode for the Activity Selection Problem in dynamic programming as opposed to Greedy Algorithm. The recurrence I have is:

c[i,j] = max(c[i,k] + c[k,j] + 1), where c[i,j] denotes the size of an optimal solution for set of activities.

So far, I have:

ACTIVITY-DYNAMIC(s, f)
    n = length(s)
    c = []
    for i to n
        c[i] = max(c[i,k] + c[k,j] + 1)

But I can't seem to figure out what to do next. Any suggestions, pointers?

share|improve this question
You should start the function by initializing the end-cases (i.e. $c[0,i]$ and $c[i,0]$ for all $i$). Then, fill the array according to the recurrence relation. Note that filling the array requires a 2-dimensional loop (traversing $i,j$), and within this loop, use an inner loop to take the maximum over $k$. – Shaull Feb 19 at 15:11
How would I pick k in this case? Also, would I fill c[0,i] and c[i,0] with zeros? – Darksky Feb 19 at 15:18
Sorry, I was thinking of something different in the previous comment. I'm not sure it's relevant here. Could you clarify how you ended up with this recurrence relation, and what exactly $c[i,j]$ denotes? – Shaull Feb 19 at 15:26
Well its the typical activity selection recurrence which I've been reading about. It's quite long to explain in a comment, but its the standard one. Here's a link that explains it: sanlp.org/daa/slides/… – Darksky Feb 19 at 15:49
Ok, so what I wrote above wasn't far off. You start by initializing the base conditions: all the cases where you already know the value of $c[i,j]$, which is exactly those where $S_{ij}=\emptyset$. These are exactly $S_{ij}$ such that $i\ge j$ (so everything below the diagonal). Now that this is filled, you can proceed with the triple loop mentioned above to fill the rest of the table bottom-up. Finally, you return $c[0,n]$. – Shaull Feb 19 at 15:59

Know someone who can answer? Share a link to this question via email, Google+, Twitter, or Facebook.

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.