Ask your own question, for FREE!
MIT 6.00 Intro Computer Science (OCW)
OpenStudy (shriram):

I'm stuck at dp problem #4 for ps 8 It takes way too long for maxWork >= 7 or so, on 320 items(subjects) in the provided subjects.txt file Code's at http://ideone.com/dpt8V Could someone tell if it could be optimized further ? I've checked a few posts that talk about a Matrix solution ,etc. but I would like to fix solution in code above. I'm probably missing something trivial in my code that's taking up too much to generate the result /solution I'm stuck at dp problem #4 for ps 8 It takes way too long for maxWork >= 7 or so, on 320 items(subjects) in the provided subjects.txt file Code's at http://ideone.com/dpt8V Could someone tell if it could be optimized further ? I've checked a few posts that talk about a Matrix solution ,etc. but I would like to fix solution in code above. I'm probably missing something trivial in my code that's taking up too much to generate the result /solution @MIT 6.00 Intro Co…

OpenStudy (anonymous):

you are not memoizing anything which is the defining feature of dynamic programming, watch the end lecture 17 (start about twenty minutes into it) and the beginning of 18 again.

OpenStudy (shriram):

I don't get it. I didn't go through the video lecture yet it but I think grasped the basic idea . I read the wikipedia entry on memoization, and if you look at the code carefully, I store values for later use on line 79 and check on line 75 if it already exists avoiding another recursive call. What more will memoize do ?

OpenStudy (anonymous):

put lots of comments in your code so we can see what you intended - this problem is hard enuf to figure out. or explain how the two functions work to accomplish the task; citing line numbers in the code line numbers

OpenStudy (shriram):

Here http://ideone.com/ALsx9

OpenStudy (shriram):

@ bwCA I figured out the problem. I setup the memoization conditions and steps but the program doesn't ever make use of it. Thanks for pointing out the it doesn't memoize anything

OpenStudy (anonymous):

post it, i like to see solutions to this one

OpenStudy (shriram):

I shall definitely post my solution as soon as I'm done. Currently, I'm still working on it

OpenStudy (shriram):

Here's a solution I've worked on but works only till maxWork < 20 I'm not sure if I get the right answers for the values from 10 to 20 but I tested it with a smaller subject list i.e of size 4 or 5. I get the right answers then. For the subject list of 320 items, my solution takes too long to compute an answer and I stop computing the answer mid-way, as it eats away a lot of memory only when I give maxWork a value of 20 or more

OpenStudy (shriram):

The solutions I get from the code in the attachment with maxWork = 6,7,8,9 with subject list given for the problem are incorrect. Ignore the code in the last attachment

OpenStudy (anonymous):

i don't understand what lines 150 thru 159 do - could you explain in words? in the for loop that begins at line 150 you call dpAdvisorhelper multiple times (line 156) - in turn dpAdvisor helper is calling itself (probably multiple times) at line 204. this seems like too much. I think tou might be doing too much in dpAdvisor - most of the solutions i have seen only call dpAdvisorhelper once from dpAdvisor. Are lines 150-159 an optimization strategy? at line 144 you 'fill' li with the list of subjects using list() why don't you just use subjects.keys()?

OpenStudy (shriram):

I finally got a working version of my previous file but it takes way too much time starting from maxWork == 7

OpenStudy (shriram):

Yes, I might be doing too much in both dpAdvisor and dpAdvisorHelper. I have to think of the design once more.

OpenStudy (shriram):

using li in line 144 gives the same result. calling 204 is the crux of the solution. in lines 150-159 , i check for the first item in subject.keys() whose work doesn't exceed maxWork and in fact less than maxWork, and then break to avoid checking further.

OpenStudy (shriram):

What I'm essentially doing or would like to do is the following: let us say keys are [1,2,3] and let us assume all keys have corresponding value of work less than maxWork Line 204 does [1,2,3]-> [1],[2,3]->[2],[3] Now I get the combination[2],[3],[2,3] after the last arrow and would then add those to [1] to get [1],[2],[3],[1,2],[1,3],[1,2,3] Out of the above, it's easy to find the one associated with the maximum Value

OpenStudy (shriram):

Here's a working solution that takes nearly 10 minutes for maxWork of 10 Hahaha. I think there's no memoization really in this solution

OpenStudy (shriram):

The subproblems are solved and solutions from each are composed from last function call to the first.

OpenStudy (anonymous):

are you saying that you are making all combinations of keys whose work is less than maxWork, then comparing those combinations?

OpenStudy (shriram):

less than or equal to maxWork. Here's an optimized version of my last solution

OpenStudy (shriram):

Finally, I've solved it. You wouldn't believe this. Lines 215 and 218 caused a delay of two days. I didn't have them before but affected the solution. Implementation issue even though the idea was right. Most importantly, I 've only started to make use of the approach of memoization only after I've actually started to accept the solution given @ http://20bits.com/articles/introduction-to-dynamic-programming/ I worked it on by hand on paper to convince myself that it covers all possibilities, had to write down all cases explicitly that might be possible starting with smaller input i.e, not more than 3 to 4 subjects. That helped a lot. Nearly a month and a week or two later, I've solved it. It is ridiculous. I would have solved it way too sooner if I had spent enough time trying to understand the text in the above mentioned link thoroughly. I couldn't believe that I didn't realize I was solving a brute force problem and tweaking that under the impression that I've actually implemented memoization technique for DP. Here's the breakdown: 15 days : tweaking brute force approach of dp 10 days : poor design for memoization approach 1 day: perfect implementation except for lines 215 and 218 today: debugging done to figure out lines 215 and 218 are necessary (there might be other ways to do this) * all days with plenty of breaks and less than an a hour or two spent on it per day

OpenStudy (anonymous):

congrats. i learned a lot on this one. if you want other ppl to see this and comment - you should create another post. i'm probably the only one that will see it cause it is so old and i'm the only other person in the conversation. give me a few days to play with this. i'll post mine and another method later

Can't find your answer? Make a FREE account and ask your own questions, OR help others and earn volunteer hours!

Join our real-time social learning platform and learn together with your friends!
Can't find your answer? Make a FREE account and ask your own questions, OR help others and earn volunteer hours!

Join our real-time social learning platform and learn together with your friends!