81–90 of 102 posts
While dynamic programming is taught in almost all algorithms classes, I think I finally grokked it after implementing it in a few practice problems. Would strongly recommend giving a few exercises listed here a shot: https://leetcode.com/tag/dynamic-programming/
Earlier quoted context omitted.
They're now using Mooshak to upload and run the tests automatically. The algorithms class is now mostly taught in Java, though.
Do you also mean FCT/UNL? Interesting, I didn't knew about it.
While dynamic programming is taught in almost all algorithms classes, I think I finally grokked it after implementing it in a few practice problems. Would strongly recommend giving a few exercises listed here a shot: https://leetcode.com/tag/dynamic-programming/
I've grokked it a couple of times, implemented solutions for some problems (knapsack, matrix multiplication, etc...), but I always keep forgetting...
However I would definitely struggle with it today. My best simplistic explanation is that it is a method in which you cache values in order to not duplicate work.
I then tell about the only example which I could still bang out on a white board, which is fibonacci with a cache.
Oh yeah and another important detail is something something solving subproblems :p
Please note, the last name of the author referenced in the article is "Trick", not Tick. http://mat.gsia.cmu.edu/classes/dynamic/dynamic.html
For the last part about economic optimization, I would not approach it with Dynamic Programming. As evidenced by go and many games, doing the "local" best move does not guarantee the best result in the end. If brute-forcing is untractable, the state-of-the-art is using Monte-Carlo Tree Search as evidenced by its dominance in board games, Magic the Gathering, Poker, robots competitions, RTS, etc ...
> Memorisation It is memoization, not memorisation! Although for two weeks in algorithms class I did in fact think our prof was just pronouncing memorize in a cutesy manner.
That's simply the British English way of writing the word. The author is a Swede and most probably got educated in the official way of writing English.
Earlier quoted context omitted.
Do you also mean FCT/UNL? Interesting, I didn't knew about it.
Yeah, I attended it until a few years ago. They're also teaching OCaml and Prolog, but Java is the main language for algos, and for the AI class too. C is only now used for the Systems class.
Back when I was there, we used Caml Light.
Miss the campus. :)
Earlier quoted context omitted.
I've grokked it a couple of times, implemented solutions for some problems (knapsack, matrix multiplication, etc...), but I always keep forgetting...
You're not alone! Went down the whole nine yards in college, and come exam time knapsack was toast! However I would definitely struggle with it today. My best simplistic explanation is that it is a method in which you cache values in order to not duplicate work. I then tell about the only example which I could still bang out on a white board, which is fibonacci with a cache. Oh yeah and another important detail is so…
Earlier quoted context omitted.
Thanks for the great explanation of tail recursion. But I still don't see how tail recursion implements memoisation? One might even argue that tail recursion is the opposite of memoisation; while tail recursion saves memory because it eliminates the need to remember previous results of function calls, memoisation on the other hand uses extra memory to save results of earlier function calls.
rishabhparikh is correct, but since the point is quite subtle it might help to be a bit more elaborate. The crux of the misunderstanding is here: [tail recursion] eliminates the need to remember previous results of function calls . Emphasis: results . The thing is: tail call recursion essentially means "finish all intermediate computations and pass the results of these to the next function call". In the non-tail call…
Ok, but isn't this then also the case for non-tail recursive calls? And ordinary recursive call builds just as well on the finished result of the previous call and no result is really "stored" in either case.
Earlier quoted context omitted.
rishabhparikh is correct, but since the point is quite subtle it might help to be a bit more elaborate. The crux of the misunderstanding is here: [tail recursion] eliminates the need to remember previous results of function calls . Emphasis: results . The thing is: tail call recursion essentially means "finish all intermediate computations and pass the results of these to the next function call". In the non-tail call…
> This is why it can be considered memoization: each recursive call builds on the "stored" finished result of the previous call. Ok, but isn't this then also the case for non-tail recursive calls? And ordinary recursive call builds just as well on the finished result of the previous call and no result is really "stored" in either case.
> You have to recurse until you reach n == 0, and only then does the whole sum "collapse".