Dynamic Progamming: First Principles • Hacker News Board

Re: Dynamic Progamming: First Principles

#21

Post by TuringNYC » Wed, Oct 25, 2017, 12:37 AM UTC

baddox wrote: post #15

krat0sprakhar wrote: post #4

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/

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

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.

Re: Dynamic Progamming: First Principles

#22

Post by chrisbennet » Wed, Oct 25, 2017, 12:38 AM UTC

throwaway7645 wrote: post #18

santaclaus wrote: post #2

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

I came on here to say that.

Me too!

Re: Dynamic Progamming: First Principles

#23

Post by gumby » Wed, Oct 25, 2017, 12:38 AM UTC

wht wrote: post #8

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 Progra…

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

Re: Dynamic Progamming: First Principles

#24

Post by TuringNYC » Wed, Oct 25, 2017, 12:39 AM UTC

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.

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.

Re: Dynamic Progamming: First Principles

#25

Post by gwern » Wed, Oct 25, 2017, 12:53 AM UTC

wht wrote: post #8

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 Progra…

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

Re: Dynamic Progamming: First Principles

#26

Post by beardbandit » Wed, Oct 25, 2017, 12:54 AM UTC

baddox wrote: post #15

krat0sprakhar wrote: post #4

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/

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

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

Re: Dynamic Progamming: First Principles

#27

Post by akhilcacharya » Wed, Oct 25, 2017, 12:55 AM UTC

krat0sprakhar wrote: post #4

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/

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

Re: Dynamic Progamming: First Principles

#28

Post by foxh0und » Wed, Oct 25, 2017, 12:55 AM UTC

santaclaus wrote: post #2

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

Thanks all!

Re: Dynamic Progamming: First Principles

#29

Post by BucketSort » Wed, Oct 25, 2017, 12:58 AM UTC

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

Re: Dynamic Progamming: First Principles

#30

Post by gugagore » Wed, Oct 25, 2017, 1:01 AM UTC

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…

I don't think it's that common to solve, say, shortest paths by solving the LP/MIP formulation (unless maybe the problem at hand isn't strictly a shortest paths problem). Is it?