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

61–70 of 102 posts

Re: Dynamic Progamming: First Principles

#61

Post by TeMPOraL »

gicadin wrote: post #49
Bromskloss wrote: post #39

Earlier quoted context omitted.

Is paper programming in pseudocode bad, though? I mean, computing science is not about computers, and all that.

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 away parts of the problem until you have a good understanding of the entire problem.

I can't even count the cases in which I though I understand some algorithm (either in uni, or more recently, through reading a paper), then I sat down to implement it and realized I don't really understand shit about it.

Re: Dynamic Progamming: First Principles

#62

Post by cdax »

misja111 wrote: post #58

> Tail recursion [3], a variant of traditional recursion implements memoisation, which uses memoisation very economically. I don't understand this part, can anybody explain?

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 - 1)    // A
When n = 1000, your function call stack will have to hold ~1000 calls (fn(1000), fn(999), fn(998), fn(997), and so on...), before it's able to compute the sum. This is because the return statement in line A above, needs to keep track of the variable `n` from the calling function in order to be able to compute the return value. If only there was some way to eliminate that variable `n`...

That's where tail-recursion or tail-call optimization comes in:

  fn sum_tail(n, pre_sum):
    if n == 0:
      return pre_sum
    return sum_tail(n - 1, pre_sum + n)    // B
    
  fn sum(n):
    return sum_tail(n, 0)
In this solution, the return statement at line B does not depend on any variable from the calling function (it simply passes that value on to next function call), and so the calling function can immediately be popped off the stack, saving stack space and making your solution more memory-efficient.

It's useful to know that whether any stack space can actually be saved, depends on whether your language of choice implements tail-call optimization. e.g., JavaScript recently started supporting tail-call optimization after ES6 [1], and Python does not support it [2].

[1] http://2ality.com/2015/06/tail-call-optimization.html [2] https://stackoverflow.com/questions/13591970/does-python-opt...

Re: Dynamic Progamming: First Principles

#63

Post by Terr_ »

et2o wrote: post #3

Favorite examples for applications of dynamic programming? Mine are sequence alignment/BLAST in bioinformatics, but I'm sure there are many of which I am not aware in other fields.

Ditto, my first "Ahah!" moment for DP was actually in a bioinformatics class, implementing Needleman–Wunsch global sequence alignment using a Blosum64 matrix door transition weights. (Details that aren't as impressive as they sound.)

I ended up using it as the basis for another extra-credit project that demonstrated the algorithm with a GUI: Select inputs, choose speed, hit Play, watch the numbers and lines, etc.

Anyway, it's stayed with me as my go-to DP example.

Re: Dynamic Progamming: First Principles

#64

Post by hvidgaard »

throwaway7645 wrote: post #19
mattkrause wrote: post #13

Earlier quoted context omitted.

What were you supposed to use instead? My impression is that dynamic programming is sometimes sluggish but often better than the alternatives.

Most optimization problems use Linear Programming if the problem has linear/continuous variables and Mixed Integer Programming if binary values (turning something on or off) is part of the solution. These are used in production pretty much everywhere. LP (linear programming) problems are extremely fast too. My company has a HUGE LP & MIP problems and the LPs are still only a few minutes to solve on nice hardware. MIP…

Unfortunately MIP (and ILP in general), is potentially really really slow, (and proved to me NP-Hard). That extra constraint of a value that must be an integer really complicates things. Still, it's a really nice way to express may optimization problems.

Re: Dynamic Progamming: First Principles

#65

Post by misja111 »

cdax wrote: post #62
misja111 wrote: post #58

> Tail recursion [3], a variant of traditional recursion implements memoisation, which uses memoisation very economically. I don't understand this part, can anybody explain?

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.

Re: Dynamic Progamming: First Principles

#66

Post by aquarin »

Bromskloss wrote: post #11
santaclaus wrote: post #5

Earlier quoted context omitted.

Image stitching is pretty fun!

That sounds like it could have some things in common with the DNA-sequence alignment of the parent comment, both dealing with overlap. Is that so?

Yes, it have a lot of common.

Re: Dynamic Progamming: First Principles

#67

Post by joshvm »

et2o wrote: post #3

Favorite examples for applications of dynamic programming? Mine are sequence alignment/BLAST in bioinformatics, but I'm sure there are many of which I am not aware in other fields.

Stereo image matching - specifically semi-global matching. The general idea is still considered a state of the art method.

Re: Dynamic Progamming: First Principles

#69

Post by quotemstr »

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.

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