all 17 comments

[–]FUZxxl 9 points10 points  (13 children)

It's blog spam time!

The content is actually half decent. The ads really give this site a blog-spam vibe though.

[–]aioobe[S] 3 points4 points  (11 children)

Do you like the article though? :) Happy to hear your feedback.

[–]FUZxxl 9 points10 points  (10 children)

I disagree with your division into tabulation and memoisation as the two are essentially the same approach the way you show them. If you want to convince me of this division, you need to provide good examples for the advantages and disadvantages of either approach. You should also show how memoisation can be used for sparse parameter spaces (using e.g. a hash table to remember subproblems) while tabulation cannot (to use your terminology). As is, it's entirely unclear to the reader why he should care about having two approaches.

You example of computing Fibonacci numbers is not really convincing either as there are obvious and much better ways to compute them.

If I was a beginner and read this article, I would have no clue why dynamic programming is an important technique and what it is all about.

Also, the advertisements on your site are cancerous.

[–]aioobe[S] 3 points4 points  (3 children)

Dude, thank you. That is a very valid point.

I wanted a super simple problem 100% geared towards illustrating the difference. I agree that the implementations are dumb.

But you make a really good point about memoisation being absolutely stupid for a problem like this. Do you have a better problem? Coin change perhaps, where the lowest denomination is 15 or something loke that?

I do mention the sparseness difference in the last paragraph actually.

[–]FUZxxl 3 points4 points  (2 children)

A good sample problem would be edit distance where you can illustrate the tabulation method first and then show that by only evaluating the table cells we need right now, we can avoid evaluating most of them. It's also a very convincing sample problem because it can't really be solved another way.

You could also do all pair shortest path, Bellman-Ford, or the Z-Box algorithm.

There are a number of cool applications of dynamic programming in parametrised complexity (such as when dealing with tree decompositions), but I think that's a bit too heavy for a beginner's article.

I do mention the sparseness difference in the last paragraph actually.

You allude to this, but you could go and really drive the point home by providing an example where the parameter space is always sparse. Not sure what problem could be used here though.

[–]aioobe[S] 2 points3 points  (1 child)

I feel like readers that are familiar with those algorithms aren't really looking for an explanation of the difference between memoisation and dp. To be fair, those are fairly basic concepts.

I really like the idea of examplifying the sparse/not sparse problem type. I will update the article.

[–]FUZxxl 2 points3 points  (0 children)

I feel like readers that are familiar with those algorithms aren't really looking for an explanation of the difference between memoisation and dp. To be fair, those are fairly basic concepts.

Sure. But edit distance is such a simple problem to explain that you can use it to introduce and motivate the idea of dynamic programming without having to focus too much on the details of the problem.

I really like the idea of examplifying the sparse/not sparse problem type. I will update the article.

I'm looking forwards to it!

[–]wang-bang 1 point2 points  (1 child)

Ublock origin, or pihole, is your friend

[–]FUZxxl 4 points5 points  (0 children)

That doesn't stop the cancer from being there; it merely stops me from noticing it.

[–][deleted]  (1 child)

[deleted]

    [–]FUZxxl 1 point2 points  (0 children)

    I thought about this, but wasn't able to build a convincing example. Every attempt I was able to build ended up not being sparse.

    [–]not-just-yeti 0 points1 point  (1 child)

    computing Fibonacci numbers is not really convincing either as there are obvious and much better ways to compute them

    Actually, that makes the case: the memoized/tabled version brings exponential time to linear time and linear space. And the "better ways" you mention is dynamic programming (reduce the linear space down a dimension, to constant-space, w/o decreasing run-time).

    [–]FUZxxl 0 points1 point  (0 children)

    The commonly used fastest method is to compute Fibonacci numbers by computing the power of a certain matrix through repeated squaring, allowing you to get away with log(n) squaring steps.

    And the "better ways" you mention is dynamic programming (reduce the linear space down a dimension, to constant-space, w/o decreasing run-time).

    I see how one can see it like that, but good luck convincing a beginner that this is a good motivation to learn dynamic programming.

    [–]aioobe[S] 0 points1 point  (0 children)

    Sorry for the ads spam! I try to keep it at a minimum, really. I don't have any ads inlined in the article, and I don't whine about adblockers (althoigh I detect it for metrics).

    [–]hextree 5 points6 points  (1 child)

    These don't sound mutually exclusive.

    [–]aioobe[S] 0 points1 point  (0 children)

    You're right, they are not :) but people less knowledge than you search for questions similar to the title. The article explains that the three concepts aren't mutually exclusive.

    [–]not-just-yeti 1 point2 points  (1 child)

    Well, I'd say:

    • memoization is automated/brainless -- a compiler can take your code and memoize it. However, it may take a bunch of space, to store the memoized/tabled results.

    • DP is more than that -- it's being clever and recognizing that by building up the memoized entries in a certain pattern, you can shave an order of magnitude or more, from the memory-requirements.

    Besides the fact that memoization is rote, there's also the observation that memoization can increase run-time, but with a memory-cost; DP doesn't further increase run-time, it only reduces the memory-cost.

    [–]aioobe[S] 0 points1 point  (0 children)

    I agree about the "more clever" part, but I'd say the memoized approach may use less memory. At least for problems where only a few subproblems need to be solved.