Question

Hi guys, the ideas of graph and dynamic programming seem confuse me a lot. In lec22's code. the subtitles indict that there is a bug in function dpShortestPath(). I don't understand that code very well. How does the bug arise?
Could any one explain that problem more concretely or just give the correct code?
lec22's code
http://dpaste.com/hold/1396904/

Answer 1

It's fun to watch the video lectures, but it's a headache to just go through the codes...

Answer 2

you need to work with it till you understand how it works. you might have to watch the lecture a few times. just keep at it till you understand it then look for the bug. to be candid it has been a long while since i went thru it and i don't recall what the bug was.

maybe go back and re-watch lecture 21 also

Answer 3

In lec23 about 24:30 , Prof Guttag claims there is a dirty little secret in python.
initializing the memo = None and doing a little bit change of code may be helpful.

Answer 4

why wouldn't you want to use a mutable object as a function argument default value ?

Answer 5

Initializing the memo = None turns out to be a wrong answer…It makes no expecting change to the program.
I think I can understand the function shortestPath() now, but still confuse about the dpShortestPath(). The only thing I am sure now is that dpShortestPath() indeed has a bug(s), and the bug must hide in the memo.

Answer 6

here is one of many explanations available for this gotcha
http://effbot.org/zone/default-values.htm

Answer 7

thanks, it begins to make a little sense to me.
But those recursive relations are still very messy.
Maybe I should take an algorithm course, then i can fully understand it.