Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Dynamic Progamming: First Principles

flawlessrhetoric.com

Post reply on HN
Print view View original

71–80 of 102 posts

Re: Dynamic Progamming: First Principles

#71

Post by rishabhparikh »

misja111 wrote: post #65
cdax wrote: post #62

Earlier quoted context omitted.

In "traditional" recursion, each recursive call is pushed onto the function call stack. This means that your recursive solution will eventually run out of memory when the number of recursive calls is more than what the function call stack can handle. e.g., consider the following recursive solution for calculating the sum of all positive integers up to a given `n`: fn sum(n): if n == 0: return 0 else: return n + sum(n…

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.

The memoization occurs in the fact that we are "remembering" the previous value (pre_sum). It's a little different in that we aren't memoizing/caching all previous values, but we are still caching the last computed values aka the "tail".

Re: Dynamic Progamming: First Principles

#73

Post by TuringTest »

quotemstr wrote: post #69
Retra wrote: post #53

Earlier quoted context omitted.

Obscure words are very well suited to esoteric subject matter where precision is needed. A particular brand of function optimization is exactly that.

What precise meaning does "memorize" denote that "memorize" wouldn't? Sometimes jargon is just jargon.

"Memoization" is only used in the context of caching results of previous function calls.

So if you see the word, you instantly know that this is the context. You wouldn't know that if you see "memorization".

Re: Dynamic Progamming: First Principles

#74

Post by cee_el1234 »

Retra wrote: post #53
quotemstr wrote: post #44

Earlier quoted context omitted.

Honestly though, we should just switch to using "memorization". It's a less obscure word that communicates the intended meaning better, IMHO.

Obscure words are very well suited to esoteric subject matter where precision is needed. A particular brand of function optimization is exactly that.

Indeed... the way information is being organized is specific enough to be given a proper term - memorization indicates just storing things in whatever form

Re: Dynamic Progamming: First Principles

#75

Post by mratsim »

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 ...

Re: Dynamic Progamming: First Principles

#76

Post by vanderZwan »

misja111 wrote: post #65
cdax wrote: post #62

Earlier quoted context omitted.

In "traditional" recursion, each recursive call is pushed onto the function call stack. This means that your recursive solution will eventually run out of memory when the number of recursive calls is more than what the function call stack can handle. e.g., consider the following recursive solution for calculating the sum of all positive integers up to a given `n`: fn sum(n): if n == 0: return 0 else: return n + sum(n…

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 version, the sum function has no results until you hit the deepest level of recursion; it is the equivalent of writing the sum out in full, which causes all that extra overhead:

    sum = n + (n-1) + (n-2) + ... + 0
You have to recurse until you reach n == 0, and only then does the whole sum "collapse".

The `pre_sum + n` bit in the second example is what fixes this. All intermediate calculations are finished and then "stored" by passing them as arguments to recursive calls. This gives the functional equivalent of a for loop:

    sum = 0
    for i in n..0:
      sum += i
This is why it can be considered memoization: each recursive call builds on the "stored" finished result of the previous call.

Re: Dynamic Progamming: First Principles

#77

Post by icebraining »

pjmlp wrote: post #59
beardbandit wrote: post #26

Earlier quoted context omitted.

When I took Algorithms II in college at a top 10 CS program, our entire class involved ZERO coding or programming of any sort.

All our classes required delivering some kind of working code, either at the end of semester, or throughout it. It was also the class that introduced us to unit tests, by having the code delivered as C library, that the teacher would link against to run her tests.

They're now using Mooshak to upload and run the tests automatically. The algorithms class is now mostly taught in Java, though.

Re: Dynamic Progamming: First Principles

#79

Post by pjmlp »

icebraining wrote: post #77
pjmlp wrote: post #59

Earlier quoted context omitted.

All our classes required delivering some kind of working code, either at the end of semester, or throughout it. It was also the class that introduced us to unit tests, by having the code delivered as C library, that the teacher would link against to run her tests.

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.

Re: Dynamic Progamming: First Principles

#80

Post by pjmlp »

TeMPOraL wrote: post #61
gicadin wrote: post #49

Earlier quoted context omitted.

Although there is a lot of merit in implementing an algorithm and not just writing pseudo code, doing it on paper has some advantages. - Its a lot quicker to sketch an algorithm on paper ( you can ignore some details which are either trivial, or irrelevant to the problem ) - At a certain level you are expected to be able to convert pseudo code into actual code - The most important part of an algorithm is knowing abou…

> you can ignore some details which are either trivial, or irrelevant to the problem The most important insight of the old saw that teaching someone builds your understanding, but being able to code it ensures you have actual, deep understanding is this: the details you ignore as "trivial" or "irrelevant to the problem" are quite likely the crucial details to understand it and make it work. You can't safely handwave…

I would say, at least speaking for myself, that is what happens most of the time.
Post reply on HN