Question

HI guys. I'm working on ps9. I've run into some trouble getting the bruteforceadvisor working. I think if i could just get a grasp on the concept of it I could probably code it myself but all my attempts aren't proper brute force algorithms. Could anyone outline how bruteforceadvisor should run please?I have no code to post because it's all wrong. Thanks in advance

Answer 1

it always helps to write down your ideas on paper - freeform at first, then try to turn that into steps/actions that need to be taken. then you try to turn that into code. try to 'chunk it up'.

i did the 2008 course - i approached this by drawing my own binary decision tree like what was presented in the lecture. Doing this helped me understand the problem a lot. Then I just tried to write my code to mimic the process of going thru the tree.

This is a knapsack problem. One difference between the pset and the lecture is that you have to preserve the things you take - in the lecture the example code only preserved the total value.

Answer 2

Thanks for that. I was trying to draw out the problem last night before I asked it here but was still having trouble visualising it. I'm gonna give watching the 2008 lecture on it a go. The 2011 doesn't explain very well I think.

Answer 3

lectures 12, 13, 14 i think

Answer 4

Super thanks. That older lecture definitely seems to be better. I generated a binary set and then created my list of all possibilities from that. Not the cleverest way I'm sure and it takes over twenty seconds to run a list that's 20 long but it's working.
Nice one.
If anyone has any suggestions for improving efficiency they'd be greatly appreciated.

Answer 5

do the 2011 lectures get into dynamic programming and memoisation?

http://www.youtube.com/watch?v=EH6h7WA7sDw

Answer 6

No it never really got onto that as far as I remember. In the 2011 course they use the method i ended up using. 0 padding a binary number and creating all possible outcomes in binary form. I'll give that video a watch later when I can. Thanks

Answer 7

I just looked ahead and memoisation is 2 lectures ahead of where I am. Looks like I'll be getting to it eventually. I'm attaching what I got working anyway. Thanks again

Answer 8

yours at dpaste
http://dpaste.com/1059130/