Question

Trying to figure out the dynamic programming question, problem 4 of set 8.

Answer 1

First of all, let me just say I'm horrible at grokking recursive code and it's taken me hours of staring and pondering just to get a tenuous grasp on what bruteForceAdvisor was doing. OK, but with that out of the way (more or less), now I'm trying to apply dynamic programming. I understand the idea with dynamic programming is to look for calculations that are repeated, and then to tell the computer to refer to a dictionary of calculations to find the value instead of redoing the calculation. But - I don't see where bruteForceAdvisor is repeating any calculations. I'm using a print statement to monitor what the program is being called with, and each set is distinct - i.e. there don't appear to be any calculations that are repeated. There must be something I'm missing, but it seems like we're trying to prevent redundancy in a function without redundancy.

Answer 2

Here's the bruteForceAdvisor code:
http://pastebin.com/RDKsRPNK

And here's an example of the calls using a 4-subject dictionary (just the bruteForceAdvisorHelper subfunction):
http://pastebin.com/mUnrucMj

So, am I missing some redundancies? there don't seem to be any....

Answer 3

Perhaps I'm not looking at the right values in looking for these redundancies - i.e. maybe I think two calculations are distinct because of irrelevant differences, when the values that actually matter for computation are in fact being repeated.

Answer 4

watch the lecture again and try to understand the fastmaxval function. the problem in pset8 is a knapsack problem. fastMaxVal can be adapted to solve it - you have to keep track of the items taken.

i also started trying to adapt the bruteforceadvisor but eventually gave up - then watched the lectures a couple more times and read more about DP and finally realized that fastMaxVal would work.

The overlap is that if you trace the path thru the decision tree the take and don't take paths overlap. it is instructive to build your own decision tree with just a few subjects (like four) and walk through it by hand till you get a feel for the mechanics of doing it.

this one takes most ppl a long time. it took me a very long time. keep at it

hope all that made sense

Answer 5

Hmmmm well I've come back to the problem after a few days and I feel I'm a bit closer but it's still very opaque to me. I adapted the knapsack code to give me the correct maximum Value possible given a maximum work, which is trivial... but I can't figure out how to get the program to give me the right list of subjects instead of just a value. So I'm trying instead to work from bruteforceadvisor. But the damn thing is driving me nuts; let me just kind of think out loud so you can see how I'm approaching this.

I understand that the three values which change upon iteration in bruteForceAdvisorHelper are i, subjectWork and subjectValue. And it looks like there are multiple instances of the same three being called up, so we are getting reiterations. But now the issue is, where do we stick in values for m? In the knapsack problem we put in values for m every time we were about to return a value: essentially, before every return statement. So here's me trying to do the same thing:

http://pastebin.com/ew78uQTa

And with exactly the same results! Furthermore irritating is the mystery of the missing print statements. In this function I have an if clause which says that if that tuple is in the dictionary, print one thing, and if it isn't, print something else. So, you would think that every time it iterates, it would be printing one or the other of those two things, right? Wrong! It only prints the first time through (where it naturally says "m not found") and then it blazes through a ton of iterations tuples without printing anything before it prints my answer, narry a print statement since. I've tried adding a few more print statements before some of the times where I add to the memo dictionary in the code, and those aren't getting called. I don't understand what the problem is doing; is it skipping parts of the code? AAAAAARRRRRGGGGGHHHHHHHHHHHHHH I'm going to have a heart attack trying to solve this problem.

Answer 6

the function you posted is named dpAdvisorHelper but at lines 25 and 30 when you try to recurse you are calling bruteForceAdvisorHelper

Answer 7

Someone else alerted me to this, but thanks ;)