Dynamic Progamming: First Principles

http://www.flawlessrhetoric.com/Dynamic-Programming-First-Principles

by foxh0und • 9 years ago

300 98 9 years ago

santaclaus2• 9 years ago

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.

throwaway76453• 9 years ago

I came on here to say that.

chrisbennet• 9 years ago

Me too!

foxh0und• 9 years ago

Thanks all!

dep_b• 9 years ago

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.

derefr• 9 years ago

If you think the parent is talking about the s/z, look back earlier in the word. Memoization (regardless of locale) doesn't have an "r".

tw1010• 9 years ago

According to the authors linkedin he is as far as I can tell born and educated in Australia. Why do you say he is from Sweden?

ram_rar• 9 years ago

Given the sad state of programming interviews. People mostly land up memorizing

quotemstr2• 9 years ago

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

Retra• 9 years ago

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

PeachPlum• 9 years ago

Memoization includes writing to disk such as a materialized view.

et2o• 9 years ago

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.

santaclaus2• 9 years ago

Image stitching is pretty fun!

Bromskloss4• 9 years ago

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?

pmalynin2• 9 years ago

Reinforcement Learning

gugagore2• 9 years ago

I think really just "Value Iteration" (which isn't just used in RL). Reinforcement Learning itself is a problem setting and there are solutions in RL that don't use dynamic programming (for example, policy gradient methods).

thechao• 9 years ago

Line breaking. The Knuth-Plass algorithm I implemented is my all-time favorite piece of code.

baddox2• 9 years ago

That’s one of my favorites too, although I remember it being one of the easier implementations from my college course. We just did it with fixed width fonts, of course, but the results were still so impressing.

Bromskloss4• 9 years ago

I guess someone have to mention finding an optimal line wrap for a paragraph of text.

https://doi.org/10.1002%2Fspe.4380111102

iandioch• 9 years ago

There are lots of interesting competitive programming problems (and their related algorithms) that involve it. For example, it was important in the solution to a problem in the UKIEPC (UK & Irish programming contest to gear up for the ACM ICPC) this past weekend: https://domjudge.bath.ac.uk/domjudge/public/problem.php?id=3... :)

mlechha• 9 years ago

All of Reinforcement Learning :)

TuringNYC2• 9 years ago

Dont need DP here since there is an obviously better iterative approach, BUT, the easiest demonstration of DP value is the naive Recursive algo for Fibonacci sequence generation vs the DP+Recursive algo.

Terr_• 9 years ago

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.

joshvm• 9 years ago

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

krat0sprakhar• 9 years ago

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/

hatred• 9 years ago

Personally, I prefer these more than the leet code problems: https://people.cs.clemson.edu/~bcdean/dp_practice/

kevintb• 9 years ago

Great resource, thank you!

baddox2• 9 years ago

It’s odd that there would be algorithms classes that don’t require some implementations.

TuringNYC2• 9 years ago

When I did Algorithms in college ~18yrs ago, I dont recall it being called DP. We certainly learned it but without a distinct name for it, it didnt hold as a unique concept, just an obvious strategy/approach.

beardbandit• 9 years ago

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

akhilcacharya• 9 years ago

Interesting that you should mention that because not being able to do those problems is why I want to learn it!

zerr2• 9 years ago

I've grokked it a couple of times, implemented solutions for some problems (knapsack, matrix multiplication, etc...), but I always keep forgetting...

fokinsean• 9 years ago

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 something something solving subproblems :p

wht• 9 years ago

In O.R. graduate School, Professor Gene Woolsey told us that he'd rise from the grave and stand on our desks screaming 'No!No!No!' if we ever actually used it to solve a practical problem.

IIRC, his complaints were about the speed of formulation, difficulty to understand and communicate the model to others, and the processing required to regenerate answers when the model changed.

I believe Optiant used Dynamic Programming for supply chain optimization.. So people do or did use it for practical problem solving. ..I think.

mattkrause2• 9 years ago

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

throwaway76453• 9 years ago

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 can be much trickier.

gumby• 9 years ago

I believe Optiant used Dynamic Programming for supply chain optimization.. So people do or did use it for practical problem solving. ..I think.

Yes, the least cost path problem is not just a classic DP problem but is an example in this article.

gwern• 9 years ago

You might be surpised how far you can get with DP on a modern computer! For example, in https://www.gwern.net/Coin-flip we consider a gambling game with 300 rounds and at least as many options each round, and while it initially sounds infeasible, you can still compute the optimal strategy in under a minute with some optimized C/C++ implementing the DP solution. Modern computers are fast. (And you can define a solution in like 5-10 lines of R/Python if you don't mind them being a lot slower. I don't know how you would solve it with LP or MIP but I suspect it will be both slower and longer.)

hyperpallium• 9 years ago

Edit distance (nee Levenshtein distance) is solved with dynamic programming, and is used by spell-checkers.

I agree reformulating the problem can be confusing. It wouldn't be worth it, but for the incredible efficiency gains (not always needed).

BucketSort• 9 years ago

Obligatory Demaine lectures - https://youtu.be/OQ5jsbhAv_M

yandrypozo• 9 years ago

that's the best set of videos about DP !!

tommsy64• 9 years ago

There appears to be a missing return statement in the Fibonacci Number example in the if block. Should look like this: https://repl.it/NLIf/1

molikto• 9 years ago

Why use monospace font?????

goerz• 9 years ago

Totally love the font!

raister• 9 years ago

Best font ever... why not?

pingiun• 9 years ago

I agree, it's hard to read

charlysl• 9 years ago

I learned it as part of speech processing, first for Dynamic Time Warping and then as the Viterbi and Baum Welch algorithms. Together with Hidden Markov Models it's a thing of beauty how it is used to model speech.

All of this is explained very intuitively in speech.zone

In the wikipedia entry there is a fun (really) explanation of why its creator called it like this.

psykotic• 9 years ago

I'm fond of this old RAND report from Dreyfus, which is worth skimming if you're mathematically inclined: Dynamic Programming and the Calculus of Variations, https://www.rand.org/content/dam/rand/pubs/reports/2006/R441...

One important takeaway is that dynamic programming in the Bellman formulation is a discrete analogue of Hamilton-Jacobi theory in how it writes down an equation for the optimal value as a function of a given endpoint rather than writing down an equation for the path as with the Euler-Lagrange equations. (You can reconstruct the path from the value function after the fact by gradient descent.) The relationship between Hamilton-Jacobi and Euler-Lagrange is the classical version of wave-particle duality. A concrete example in geometrical optics is the eikonal equation, a Hamilton-Jacobi type PDE, versus the geodesic equation, an Euler-Lagrange type ODE. Not coincidentally, one common numerical method for the eikonal equation called the fast marching method is a dynamic programming algorithm, very similar to Dijkstra's algorithm for shortest paths.

It should be mentioned that any "local" equation like a PDE or ODE cannot describe a globally optimal solution without strong assumptions such as convexity. In fact, satisfying the Euler-Lagrange equation isn't even sufficient for local optimality without further qualifications (Weierstrass conditions). But the Bellman dynamic programming equation, being recursive, can describe globally optimal solutions.

mlevental• 9 years ago

understand basically all of you've said here except this:

The relationship between Hamilton-Jacobi and Euler-Lagrange is the classical version of wave-particle duality.

in what sense are two formalisms (hamiltonian and lagrange) related to the relationship between time and freq space for fourier solutions to pdes?

also holy shit i would pay pretty good money for a service that typeset these old monographs using latex.

kbenson3• 9 years ago

Seems like in a world where there's on-demand photoshop editing through a gig economy, something like this should be feasible, if not already exist. Maybe a separate cost per page for text, diagram or both, and a system to pay other people to review pages for correctness (mechanical turk style, or just actually use mechanical turk), and you have a nifty way to update old scanned documents while helping put food on some poor grad student's table.

HHest• 9 years ago

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

matt4077• 9 years ago

Together with memo(r)ization, and the typo in the title, I'm starting to thing the letter 'R' is having a bad day.

misja1113• 9 years ago

Tail recursion [3], a variant of traditional recursion implements memoisation, which uses memoisation very economically.

I don't understand this part, can anybody explain?

cdax• 9 years ago

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

misja1113• 9 years ago

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.

smitherfield• 9 years ago

NB: Although the ES6 spec requires TCO, it turned out to present significant implementation challenges, so it's only implemented in WebKit (Safari), and is, IIRC, marked WONTFIX in V8 (Chrome, Node), SpiderMonkey (Firefox) and Chakra (Edge). There's a good chance it'll get removed from a later edition of the standard.

fmihaila• 9 years ago

Glaring typo in the title: it should say progRamming.

mratsim• 9 years ago

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

sacado2• 9 years ago

Constraint solving works pretty well in these domains too, and AFAIK, top-level artificial players in board games is a mix of constraint solving and MCTS.

yipopov• 9 years ago

Would it have killed him to use a proportional font? We have the technology to accomplish that now.

Dynamic Progamming: First Principles

Related Stories