ps8 prob 4- I spent a couple of days trying to wrap my head around this problem and follow the fastmaxval code given in lecture. I decided to post my strategy and solution. I am basically using the fastmaxVal code but adjusting it to return a tuple of (value, (list of indexes where the value came from) ie if the value is a sum of values then the list will have more than one index in it. anything that returns 0 retuns an empty list. Use a concatenation function to add the value portions of 2 tuples together and the list portions together. http://codepad.org/YCK1qS3B

Question

ps8 prob 4- I spent a couple of days trying to wrap my head around this problem and follow the fastmaxval code given in lecture.  I decided to post my strategy and solution.  I am basically using the fastmaxVal code but adjusting it to return a tuple of (value, (list of indexes where the value came from) ie if the value is a sum of values then the list will have more than one index in it.  anything that returns 0 retuns an empty list.  Use a concatenation function to add the value portions of 2 tuples together and the list portions together.  http://codepad.org/YCK1qS3B

anonymous · Answer

sour solution looks similar to what i did.  i compared your results with mine for various work values (using the full dictionary) and they were the same.

yours is faster than mine as work increases.  yours looks linear with work, mine is a bit more than linear (not quite quadratic) - i'm going to have to figure that out.

yours is blue, mine is red, green is the difference.  milliseconds on the y axis and work on the x