Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Dynamic Programming vs. Divide-and-Conquer (2018)

trekhleb.dev

Post reply on HN
Print view View original

51–60 of 120 posts

Re: Dynamic Programming vs. Divide-and-Conquer (2018)

#51

Post by ketzu »

goldenkey wrote: post #43

vs Pure Reason Reason gets you a closed form for F(n), the nth Fibonacci number. The author's naive fib with memoization is O(n). The closed form is O(1) if you consider exponentiation to be a constant time operation. https://en.m.wikipedia.org/wiki/Fibonacci_number#Closed-form... Quite a thing to overlook in an article about efficiency of algorithms... why am I not surprised?

My understanding why this is usually not discussed is the following: The fibonacci sequence is usually used as an illustrative example or motivating problem for a given topic, not as a problem in itself. I believe a side note might most likely detract from the overall point for a technicality.

For the same reason you only wrote "if you consider exponentiation to be a constant time operation" instead of including a side analysis of how everything changes once you can't do that anymore, possible problems with accuracy of floating point representations of phi and it's exponentiation and everything else one has to consider once we leave the comfortable home of architecture native integers.

It is usually very valid to do so.

Re: Dynamic Programming vs. Divide-and-Conquer (2018)

#52

Post by lifthrasiir »

EvilEy3 wrote: post #48
lifthrasiir wrote: post #42

Earlier quoted context omitted.

There are only a few useful parts of the algorithm theory in practice. The time complexity is surely one of them, but it is still overvalued in a sense that the actual performance on the real hardware and realistic input distribution is more important. And when you actually need algorithms, you always have a luxury of existing literatures and implementations. Real-time algorithm design in the interview is very unreal…

> And when you actually need algorithms, you always have a luxury of existing literatures and implementations. And how well that works in practice? How will candidate even know where to look at if he has no idea what he needs to find?

> How will candidate even know where to look at if he has no idea what he needs to find?

That happens all the time, not just for algorithms. I don't expect candidates to know every possible algorithm (as I surely don't), I expect candidates to identify and learn what's required for the task. A knowledge of the specific algorithm is not of much value. The ability to learn and possibly implement algorithms is.

Re: Dynamic Programming vs. Divide-and-Conquer (2018)

#54

Post by ketzu »

da39a3ee wrote: post #32

Looks great, bookmarked. A big problem with explaining/learning this area is the name. Names are important but unfortunately the name "dynamic programming" is, according to the people responsible for choosing the name, just BS that they made up one day for their employer.

> unfortunately the name "dynamic programming" is, according to the people responsible for choosing the name, just BS that they made up one day for their employer.

For people interested, Richard Bellman who apparently came up with the name, put down the story in his autobiography which is cited on wikipedia: https://en.wikipedia.org/wiki/Dynamic_programming#History

"I spent the Fall quarter (of 1950) at RAND. My first task was to find a name for multistage decision processes. An interesting question is, "Where did the name, dynamic programming, come from?" The 1950s were not good years for mathematical research. We had a very interesting gentleman in Washington named Wilson. He was Secretary of Defense, and he actually had a pathological fear and hatred of the word "research". I’m not using the term lightly; I’m using it precisely. His face would suffuse, he would turn red, and he would get violent if people used the term research in his presence. You can imagine how he felt, then, about the term mathematical. The RAND Corporation was employed by the Air Force, and the Air Force had Wilson as its boss, essentially. Hence, I felt I had to do something to shield Wilson and the Air Force from the fact that I was really doing mathematics inside the RAND Corporation. What title, what name, could I choose? In the first place I was interested in planning, in decision making, in thinking. But planning, is not a good word for various reasons. I decided therefore to use the word "programming". I wanted to get across the idea that this was dynamic, this was multistage, this was time-varying. I thought, let's kill two birds with one stone. Let's take a word that has an absolutely precise meaning, namely dynamic, in the classical physical sense. It also has a very interesting property as an adjective, and that is it's impossible to use the word dynamic in a pejorative sense. Try thinking of some combination that will possibly give it a pejorative meaning. It's impossible. Thus, I thought dynamic programming was a good name. It was something not even a Congressman could object to. So I used it as an umbrella for my activities."

Re: Dynamic Programming vs. Divide-and-Conquer (2018)

#56

Post by EvilEy3 »

lifthrasiir wrote: post #52
EvilEy3 wrote: post #48

Earlier quoted context omitted.

> And when you actually need algorithms, you always have a luxury of existing literatures and implementations. And how well that works in practice? How will candidate even know where to look at if he has no idea what he needs to find?

> How will candidate even know where to look at if he has no idea what he needs to find? That happens all the time, not just for algorithms. I don't expect candidates to know every possible algorithm (as I surely don't), I expect candidates to identify and learn what's required for the task. A knowledge of the specific algorithm is not of much value. The ability to learn and possibly implement algorithms is.

> I expect candidates to identify and learn what's required for the task

And that comes for free in people who spent time on Algorithms and Data Structures.

Re: Dynamic Programming vs. Divide-and-Conquer (2018)

#57

Post by slt2021 »

EvilEy3 wrote: post #46
nicoburns wrote: post #37

Earlier quoted context omitted.

There are plenty of people who have a fantastic knowledge of CS theory and are pretty useless at solving real world problems.

> solving real world problems Define this first.

changing color of a button in an Electron app, or moving JSONs back and forth (from backend to frontend)

Re: Dynamic Programming vs. Divide-and-Conquer (2018)

#58

Post by lifthrasiir »

EvilEy3 wrote: post #56
lifthrasiir wrote: post #52

Earlier quoted context omitted.

> How will candidate even know where to look at if he has no idea what he needs to find? That happens all the time, not just for algorithms. I don't expect candidates to know every possible algorithm (as I surely don't), I expect candidates to identify and learn what's required for the task. A knowledge of the specific algorithm is not of much value. The ability to learn and possibly implement algorithms is.

> I expect candidates to identify and learn what's required for the task And that comes for free in people who spent time on Algorithms and Data Structures.

Yes, I haven't said that you should not learn algorithms. The best way to learn that skill is to learn (some) algorithms; DP is particularly worthwhile to learn because it is pretty hard to invent by one's own. But as an interviewer I would spend more time to check the general ability to adapt than the algorithmic knowledge.

Re: Dynamic Programming vs. Divide-and-Conquer (2018)

#59

Post by zozbot234 »

DaiPlusPlus wrote: post #45
Bancakes wrote: post #38

Earlier quoted context omitted.

It's not just the algorithm, but the frame of mind to consider an optimisation. I guess it's a rare sight in the age of electron apps and cloud startups.

Oh c'mon... Electron apps aren't slow, bloated, and awkward because the new junior SWE on the team used a O(n^2) tree-walking algorithm for the app's search feature - they're like that because it's inherent in using a general-purpose web-browser engine for your desktop GUI. Micro-optimizing application software programs by implementing different algorithms is completely detached from the big engineering choices made…

> Electron apps aren't slow, bloated, and awkward because the new junior SWE on the team used a O(n^2) tree-walking algorithm for the app's search feature - they're like that because it's inherent in using a general-purpose web-browser engine for your desktop GUI.

¿Por qué no los dos? If we're going to implement a desktop GUI via a general-purpose web browser, it should at least be as fast as a generic webpage.

Re: Dynamic Programming vs. Divide-and-Conquer (2018)

#60

Post by anon_tor_12345 »

i'm late to the comments but hopefully this helps someone:

i struggled with DP as much as anyone. i read all of the standard resources (CLRS, vazirani, kleinberg, etc), watch all the youtube videos, did all of the practice problems in the books, and still couldn't solve the kinds that are asked on interviews. i even went as far as emailing kleinberg for help.

what made it basically unconsciously fluent for me (i.e. i can read a problem statement and sketch out the recursion and subproblems in about 60s and then just perform fixup) was doing hordes of them on leetcode in preparation for a FB interview. it got to the point where i could solve hard ones in about 5 minutes using either bottom-up or top-down (i.e. memoization). so if you're struggling with DP for interviews my suggestion (which is basically the standard suggestion) is to just grind the problems on leetcode.

and contrary to popular belief they do come up outside of interviews - i had to solve a circuit synthesis problem last week and it turned out to be basically DP substring counting problem. took me all of 5 minutes.

Post reply on HN