Question

Who is on problem set 8? I need help in figuring out how the bruteForceAdvisor() function works.
What bothers is that if I'm to implement a similar function myself, where should I start thinking about it? I would like to untangle this problem and understand it completely.

Answer 1

2008 course? did you understand the functions presented in the knapsack lecture?

Answer 2

yes, 2008, and yes, I think I understand the functions in the knapsack lecture

Answer 3

so this is a knapsack problem and it can be solved with an algorithm similar to the function shown in the lecture. that function can be adapted to the specifics of this problem. walking through the 'binary' decision tree is a good way to understand the mechanics of what needs to be done. I made my own tree (just like what was shown in the lecture) but used the specifics for this problem - i had to go through it a few times before i started to get a feel for it.

Answer 4

The bruteforce algorithm creates every possible variation and then selects the best out of those. In problem set 8, you do not need to create the brute force algorithm, but you will be analyzing its efficiency in contrast to the dynamic programming algorithm.

Now, I think you are saying that even though the problem set doesn't require you to create the brute force algorithm, you would like to understand how it is created. I think we created a brute force algorithm in the word games problem sets. On the other hand, I think that brute force algorithm only chose--what was the term--the locally best solution and not the globally best? that is, it only created the best word from the hand, it didn't maximize the points available from the hand. But then again, you would pretty much never want to do that, because you will always be using dynamic programming to solve those problems.

Answer 5

@bwCA initially I thought I might use memoization to their brute force algorithm by adding and modifying some lines of it but you say that you built up dpAdvisor from scratch based on the binary tree algorithm provided in lecture 13, right?
@pdiddy you're absolutely right, i want to understand how bruteForceAdvisorHelper works and moreover i want to be able to reproduce such or similar algorithm, in other words i would like to master it
now i don't have a clue how it works, there are soooo many parameters and there are two recursive calls and multiple return points

i would appreciate if somebody provides me some links to relatively straight forward resorces that can help tackle recursive functions

Answer 6

I don't think you should try to hard to understand the brute force in this problem set. there is a reason they do it for you. I would trust their pedogogy. If you want to investigate brute force I would revisit some earlier lectures and look at your word games algo. In that one I am pretty sure we used brute force.

to solve the dynamic programming problem try to use the structure of the program in the lecture handout.

Answer 7

I believe he function is called maxval