A community for students.

Here's the question you clicked on:

55 members online
  • 0 replying
  • 0 viewing

anonymous

  • 5 years ago

pset 8 problem 4 ?? it took me a long time to do this one. I used a test dictionary with only 4 items and it worked. I'd like to compare results using the 320 item dictionary from the problem set . tia These are my results, anyone get the same? different?: with work constraint = 5 result: Total Value: 41 Total Work: 5 with work constraint = 10 result: Total Value: 70 Total Work: 10 with work constraint = 20 result: Total Value: 114 Total Work: 20 with work constraint = 40 result: Total Value: 177 Total Work: 40 thnxpset 8 problem 4 ?? it took me a long time to do this one. I used

  • This Question is Closed
  1. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    i didn't understand ur question

  2. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    I wrote a program for pset8 problem four that i think works but I haven't taken the time to figure out the optimal results by hand so I'd like to compare my results with others so that I will have confidence in my solution - so I guess it wasn't actually a question. Those results are posted above. Anyone want to share? Also (more importantly i guess)- just because my results may be right doesn't mean that I wrote an optimal solution so i would like to also compare the number of calls for the recursive part - if you are game. Here's what I got: work = 5 numcalls: 2112 work = 10 numcalls: 4272 work = 15 numcalls: 6852 work = 20 numcalls: 9803 work = 30 numcalls: 16080 work = 40 numcalls: 22308 for the number of calls, i'm not looking for precise comparisons but I'm curious how the 'magnitude' compares and how it changes with work. thnx

  3. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    man, im stuck on this one....gonna sleep on it

  4. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Got the same results than you! Actually that makes me feel better about mine as well :)

  5. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    thnx

  6. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    yeay!!.... numcalls too??

  7. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    yours is faster...

  8. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    hmm - a lot different or about the same magnitudes?? did you get in the 'thousands' for work = 5 and 10? And did it seem to increase by a little more than 2 each time you doubled the work?

  9. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    The rate of growth was about the same, but was almost twice your numbers

  10. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    If you don't mind posting your functions, I'd like to figure out why there is a difference between ours. I think it will help me understand it better, Even though mine works I'm not sure I completely understand it. here's mine...... hope its not too unreadable, i left a bunch of comments and prit statements in it.

    1 Attachment
  11. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Mine is also not very readable, let's see if we can figur out the differences

    1 Attachment
  12. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    I did a quick comparison and they both look pretty much the same except - At line 300/304 yours has an if/else statement: you compare the with and without results inside of this else clause -and memoize and return the greater of the two. Mine has the same if/else statement at lines 157/160 except I do the take and dont_take comparison (starting at line 168) outside of the else clause (also memoizing and returning the greater of the two) I haven't had time to play with yours so I don't know if this difference is making the performance different. It is interesting though that this is the part of my code that I don't understand - originally i thought my lines 168 - 190 would only be executed once in the topmost recursion (did that make sense?) but when I put a print statement at line 188 I found that it gets executed multiple times - so i was confused again. I haven't revisited that til now - guess i'm going to have to figure it out.

  13. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Because the relationship between mine and yours is that mine is about twice as big as your but the rate of change doesn't really change, maybe it has to do with the fact that I store in my memo the index of the solution plus the associated total value, while you handle the total value in dpadvisor (instead of dpadvisorHelper) can this be the difference?

  14. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    i'll have to think about that. I'm tempted to say that storing the value as well as the index shouldn't cause the number of calls to be greater. The idea of the memo is to reduce the number of calls - and that should rely on the dictionary keys not the dictionary values - we both use the same thing for a key I actually thought yours handled that better - grabbing the value right then when it was available instead of mine that has to recreate it again. The only structural difference i see is at the end there where you test inside the else clause and i test outside it - maybe mine gets to the test more often and can memoize more 'whole branches'. maybe I'll put a print statement in at the test and see there is difference on how often that happens.

  15. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    You might want to look at my heavily annotated version: http://codepad.org/Krm2BRz6

  16. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    yep i've seen that one before - way more efficient. unfortunately i didn't spend enuff time understanding that 20bits article and went off trying to mimic the decision tree process using a dictionary for the memo

  17. Not the answer you are looking for?
    Search for more explanations.

    • Attachments:

Ask your own question

Sign Up
Find more explanations on OpenStudy
Privacy Policy

Your question is ready. Sign up for free to start getting answers.

spraguer (Moderator)
5 → View Detailed Profile

is replying to Can someone tell me what button the professor is hitting...

23

  • Teamwork 19 Teammate
  • Problem Solving 19 Hero
  • You have blocked this person.
  • ✔ You're a fan Checking fan status...

Thanks for being so helpful in mathematics. If you are getting quality help, make sure you spread the word about OpenStudy.

This is the testimonial you wrote.
You haven't written a testimonial for Owlfred.