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

41–50 of 102 posts

Re: Dynamic Progamming: First Principles

#41

Post by throwaway7645 »

mattkrause wrote: post #36
throwaway7645 wrote: post #19

Earlier quoted context omitted.

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…

That's not a drop-in replacement for dynamic programming though, is it? Can you do something like edit distance with IP?

Yea, I'm not familiar with Dynamic Programming, but it sounds different. I'm talking about garden variety optimization problems (minimize or maximize something).

Re: Dynamic Progamming: First Principles

#43

Post by hyperpallium »

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…

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

Re: Dynamic Progamming: First Principles

#44

Post by quotemstr »

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.

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

Re: Dynamic Progamming: First Principles

#45

Post by gicadin »

throwaway7645 wrote: post #41
mattkrause wrote: post #36

Earlier quoted context omitted.

That's not a drop-in replacement for dynamic programming though, is it? Can you do something like edit distance with IP?

Yea, I'm not familiar with Dynamic Programming, but it sounds different. I'm talking about garden variety optimization problems (minimize or maximize something).

Dynamic Programming is one of the most common tools when doing optimization.

Generally, shortest path algorithms rely on dynamic programming for a reasonable solution. Examples of include the Traveling Salesman.

Re: Dynamic Progamming: First Principles

#46

Post by farresito »

Bromskloss wrote: post #39
megaman22 wrote: post #34

Earlier quoted context omitted.

Same. Probably the worst class I ever took was my algorithms and data structures class. I swear the professor transcribed most of CLRS onto the blackboard over 10 weeks verbatim, and we never so much as touched a keyboard.

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

Honestly, it's hard to completely grok a concept until you have solved at least a couple or three problems about the topic, no matter how many examples or lines of pseudocode you have seen. I think that's his complain, and I have to agree with him. I also took a class some years ago that was purely theoretical and I didn't really learn much besides some general concepts.

Re: Dynamic Progamming: First Principles

#47

Post by pmalynin »

gugagore wrote: post #31
pmalynin wrote: post #7

Earlier quoted context omitted.

Reinforcement Learning

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

Well of course :) but it’s a cute method to solve certain MDPs

Re: Dynamic Progamming: First Principles

#48

Post by Bromskloss »

farresito wrote: post #46
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.

Honestly, it's hard to completely grok a concept until you have solved at least a couple or three problems about the topic, no matter how many examples or lines of pseudocode you have seen. I think that's his complain, and I have to agree with him. I also took a class some years ago that was purely theoretical and I didn't really learn much besides some general concepts.

I was actually referring to solving problems yourself in pseudocode on paper.

In any case, I'm happy with a computer science course that doesn't involve actual computer implementations, and it's not just because it drives home the point that they are different things, but also because you don't have to get bogged down in the practicalities of wrestling with a particular language or a particular toolchain.

Re: Dynamic Progamming: First Principles

#49

Post by gicadin »

Bromskloss wrote: post #39
megaman22 wrote: post #34

Earlier quoted context omitted.

Same. Probably the worst class I ever took was my algorithms and data structures class. I swear the professor transcribed most of CLRS onto the blackboard over 10 weeks verbatim, and we never so much as touched a keyboard.

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 about it and what problems it solves (and variations). As well as the "trick" that makes it solve something particularly well - dynamic programming for solving sub problems etc... Even if I implement an algorithm or just write the pseudo code, I will forget the details fairly quickly, but the takeaway is that I know that for problems of type X I can use algorithms of type Y, (and sometimes i'll remember I can use Y because of fact C related to that particular problem or algorithm)

Post reply on HN