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

101–110 of 120 posts

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

#101

Post by [deleted] »

rmk wrote: post #86
dominotw wrote: post #81

Earlier quoted context omitted.

> on interviews they want you to explicitly construct the array very often i.e. it's the different between hire and a strong hire exactly because @lru_cache is much easier are you serious? someone really asked you to "use array". Beyond stupid if they really did. > you can easily blow the stack for real production grade implementations using recursion recursive solution doesn't automatically mean using a the method s…

It's not stupid to use an array, because it's the most natural data structure for representing one, two or more variables that can have different ranges and capturing their values. For example, if I have a function 'foo(a, b, c)' and I am using subproblems whose solutions use smaller values of a, b, and c, then the most natural solution is to tabulate the solutions in a 3-d array with the (fixed) values of a, b, and…

[deleted]

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

#102

Post by JadeNB »

anon_tor_12345 wrote: post #80
crazypython wrote: post #77

Earlier quoted context omitted.

DP is basically brute-force but you can reuse some of the subproblems. Another approach is trying to find a "starting point" and solving subproblems. Imagine an array of problems and starting at the left.

>DP is basically brute-force but you can reuse some of the subproblems. this is like saying "integration is basically weighing a bunch of buckets but the buckets are really small" cool but that won't help you find the correct trig sub to perform the integral. anyone that's familiar with the calc grind knows getting a good grade for the anti-derivative (indefinite integral) module is about the number of exercises you'…

> "integration is basically weighing a bunch of buckets but the buckets are really small"

> cool but that won't help you find the correct trig sub to perform the integral. anyone that's familiar with the calc grind knows getting a good grade for the anti-derivative (indefinite integral) module is about the number of exercises you've done rather than the conceptual understanding.

I am a mathematician and teacher of mathematics.

Understanding the first point is way more valuable than teaching the second. I have to ask and grade trigonometric-substitution problems for my Calculus II class because the curriculum includes it, but I'd way rather have a student come out of my class with a solid understanding of why your quoted statement about integration is true than to be able to find just the right substitution but have no idea why. They can look up the trigonometric-substitution stuff when they need it.

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

#103

Post by anon_tor_12345 »

JadeNB wrote: post #102
anon_tor_12345 wrote: post #80

Earlier quoted context omitted.

>DP is basically brute-force but you can reuse some of the subproblems. this is like saying "integration is basically weighing a bunch of buckets but the buckets are really small" cool but that won't help you find the correct trig sub to perform the integral. anyone that's familiar with the calc grind knows getting a good grade for the anti-derivative (indefinite integral) module is about the number of exercises you'…

> "integration is basically weighing a bunch of buckets but the buckets are really small" > cool but that won't help you find the correct trig sub to perform the integral. anyone that's familiar with the calc grind knows getting a good grade for the anti-derivative (indefinite integral) module is about the number of exercises you've done rather than the conceptual understanding. I am a mathematician and teacher of ma…

But we're not talking about hypothetical pedagogy here. Exams cover usub and trig sub and methods of partial fractions. In fact we're not even talking about calc at all but software interviews, which, like or it not, examine tricks.

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

#104

Post by DaiPlusPlus »

Apocryphon wrote: post #98
jorl17 wrote: post #50

Earlier quoted context omitted.

People in these arguments always talk about the algorithms, but I think that entirely misses the point. It rarely is about the algorithms themselves, but, rather, it's about the data structures. One is obviously tied to the other, but what I mean is that many slow apps are slow because the people just used the wrong data structure. Sometimes it's as simple and silly as using a list and constantly iterating over it in…

> Sometimes it's as simple and silly as using a list and constantly iterating over it instead of using a dictionary/KV-map. It's pretty easy to walk away from an algorithms course with the very basic intuitive understanding that "dictionaries trump all other data structures." Certainly that misses out on all of the cases when hash maps are a liability, e.g. when dealing with sequential data, but most questions end up…

A dictionary is an interface, not a structure.

Hashmaps, priority-queues/heap-trees, and others are all wildly different approaches of implementing a dictionary - all with their own different Big-O characteristics.

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

#105

Post by da39a3ee »

rory wrote: post #71
ketzu wrote: post #54

Earlier quoted context omitted.

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

I originally had trouble with this term because I learned about it after learning the unrelated (afaict) terms "dynamic programming language" and "dynamic typing". So perhaps it's not so much that dynamic programming was a bad choice when it was named, but that we've overloaded the term "dynamic" too much since then.

Hang on, did you read the quote above from the guy that named it?! He says explicitly that he chose it not because it was accurate but because non-technical employers/funders would be unlikely to object since it sounds positive. Does that not meet your definition of "bad choice" for a technical term?

"dynamic programming language" means a "dynamically typed" language; and "dynamically typed" means the types are acquired at run time, and vary at run time according to run time events. So "dynamic" is a good choice there in that it is consistent with the use of the word outside programming.

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

#107

Post by strikelaserclaw »

tracyhenry wrote: post #15

Merge sort seems to be a more classic example for divide-and-conquer which involves merging the results from two subproblems.

i personally like quick sort because it leads to understanding other divide and conquer algorithms like finding the kth order statistic.

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

#108

Post by chalst »

thealig wrote: post #35
chalst wrote: post #31

The paradigmatic example of a DP algorithm for me is the simple DP solution of the 0-1 knapsack problem, which, although because of NP-hardness of the general case, becomes infeasible on many easily constructed cases, actually performs pretty well on many non-artificial examples. It's an example of what the article calls bottom-up dynamic programming, but I think it is a poor example of divide-and-conquer, because it…

The example given in the article for bottom-up DP is edit distance, unless you're referring to something I missed?

I was commenting on the high-level claims of the article, not the specific algorithms the article describes. When you move from the article's example of a DP algorithm to the simple implementation I sketch of the 0-1 knapsack problem, the claim that DP is a kind of divide-and-conquer looks harder to sustain.

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

#109

Post by [deleted] »

globular-toast wrote: post #39
slumpt_ wrote: post #28

Earlier quoted context omitted.

It’s not. Theory can be referenced. People do not work in a vacuum. Interviewing in eng is broken, but afaict its a “worst solution save all others” kind of scenario. But let us not begin to deem these intrinsically important. Some of the most creative and productive coworkers I’ve had struggled with leetcode style interviews. They’re a bad tool for anyone who isnt a new grad, and even then.

When you apply for jobs do you simply look for "engineering" positions? Why am I always applying for software engineering and not electrical engineering? It's all engineering, and theory can be referenced, right? In fact, why doesn't everyone just buy a book and become a top engineer? The point is not (or shouldn't be) to recite a textbook. The point is you can navigate your way around the textbooks. I've got both Th…

[deleted]

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

#110

Post by slumpt_ »

EvilEy3 wrote: post #44
slumpt_ wrote: post #28

Earlier quoted context omitted.

It’s not. Theory can be referenced. People do not work in a vacuum. Interviewing in eng is broken, but afaict its a “worst solution save all others” kind of scenario. But let us not begin to deem these intrinsically important. Some of the most creative and productive coworkers I’ve had struggled with leetcode style interviews. They’re a bad tool for anyone who isnt a new grad, and even then.

> It’s not. Yes it is. > Theory can be referenced How do you know that the person is even able to comprehend theory? > Interviewing in eng is broken, but afaict its a “worst solution save all others” kind of scenario. That's your opinion. > Some of the most creative and productive coworkers I’ve had struggled with leetcode style interviews. Good for you. But "slumpt_'s most creative and productive coworkers" is not a…

My best coworkers is about as good of a metric as things that “stretched your mind to its limits.”

The point is neither is demonstrated to bear any relationship to jack shit

Interviewing is and has been broken, even with the changes we’ve made over the years.

If you’re holding onto leetcode challenges that make you think hard as representative of engineering prowess we’re never going to have a reasonable conversation.

Post reply on HN