5 ms·

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 aw

by et2o 9y 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.

santaclaus 9y ago
Image stitching is pretty fun!
- Bromskloss 9y 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?
  - aquarin 9y ago
    Yes, it have a lot of common.
deleted 9y ago
[deleted]
pmalynin 9y ago
Reinforcement Learning
- gugagore 9y 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).
  - pmalynin 9y ago
    Well of course :) but it’s a cute method to solve certain MDPs
thechao 9y ago
Line breaking. The Knuth-Plass algorithm I implemented is my all-time favorite piece of code.
- baddox 9y 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.
Bromskloss 9y ago
I guess someone have to mention finding an optimal line wrap for a paragraph of text. https://doi.org/10.1002%2Fspe.4380111102 https://doi.org/10.1002%2Fspe.4380111102
iandioch 9y 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=34 https://domjudge.bath.ac.uk/domjudge/public/problem.php?id=3... :)
mlechha 9y ago
All of Reinforcement Learning :)
TuringNYC 9y 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_ 9y 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 9y ago
Stereo image matching - specifically semi-global matching. The general idea is still considered a state of the art method.

by et2o 9y 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.

santaclaus 9y ago

Image stitching is pretty fun!

Bromskloss 9y 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?
- aquarin 9y ago
  Yes, it have a lot of common.

deleted 9y ago

[deleted]

pmalynin 9y ago

Reinforcement Learning

gugagore 9y 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).
- pmalynin 9y ago
  Well of course :) but it’s a cute method to solve certain MDPs

thechao 9y ago

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

baddox 9y 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.

Bromskloss 9y ago

I guess someone have to mention finding an optimal line wrap for a paragraph of text. https://doi.org/10.1002%2Fspe.4380111102 https://doi.org/10.1002%2Fspe.4380111102

iandioch 9y 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=34 https://domjudge.bath.ac.uk/domjudge/public/problem.php?id=3... :)

mlechha 9y ago

All of Reinforcement Learning :)

TuringNYC 9y 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_ 9y 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 9y ago

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