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

31–40 of 120 posts

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

#31

Post by chalst »

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 naturally fits the following purely functional form:

h(foldr f a weights)

where weights is the problem, expressed as a list of (item, weight) pairs, and f, h and a are subfunctions. This is a pretty paradigmatic non-divide-and-conquer form in functional programming: it's a one-at-a-time iteration through the list expressing the problem

So while I think this is good article with plenty of food for thought, I reject the central claim.

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

#32

Post by da39a3ee »

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.

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

#33

Post by limoce »

Labo333 wrote: post #3

I think that what the author calls "divide and conquer" is actually "recursion". Also the complexity of naive fibonacci is exactly the fibonacci sequence so O(2^n) is correct but less precise than O(phi^n)

Seems you got down-voted. I guess you're doing competitive programming? People that are good at CP never call "recursion with memoization" as "divide and conquer". Yeah, they just call it recursion.

"Divide and conquer" in CP world seems to be specific to those problems whose subproblems are not overlapping (therefore completely "divided"), e.g. merge sort, segment trees.

Considering the classic problem "Tower of Hanoi", is it "divide and conquer"? No to CP people, and even Wikipedia [0] does not explicitly regard it as "divide and conquer".

[0]: https://en.wikipedia.org/wiki/Tower_of_Hanoi

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

#34

Post by philips4350 »

tarsinge wrote: post #30
water8 wrote: post #2

The ratio of importance placed on these algorithm design in interviews vs the amount of times they actually come up in real world problems seems skewed IMO.

I do mostly not too sophisticated web apps and binary search and minimum edit distance do come up regularly. I agree you don't have to remember the implementation details, but you have to know they exist and which problems they solve.

But that doesn't mean you need to be able to implement them though. Shouldn't having a high level knowledge about these problem be enough if all you are doing is building apps.

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

#35

Post by thealig »

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?

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

#36

Post by teachingassist »

tekkk wrote: post #23
mightymercado wrote: post #4

Earlier quoted context omitted.

I would argue that it's a pretty good measure of programming and CS problem solving skill with weak alternatives.

You'd think so, but from my experience the folk that are very interested in algorithmic design and so forth produce highly abstract and hard to understand solutions to simple problems, which, in the end, are the majority in the regular dev work. Sure if you're applying for a job that really demands algorithmic design skills it should be a great asset but in general the most valuable skills any programmer has is produ…

This is a nice point -

I'd answer this type of algorithm question in truth by identifying the relevant library wherever possible, not by coding it myself, and I'd strongly expect anyone I was working with to do the same.

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

#37

Post by nicoburns »

globular-toast wrote: post #27
wst_ wrote: post #25

Earlier quoted context omitted.

It's much better to give a candidate a simplified version of your typical daily task. Give them enough time so they can google and learn if needed. That usually means very simple task that you could solve in hour or two at your leisure at home. Now, I do get that there's a lot of people who don't like spending time at home for interview tasks but when you think about AND it's not skewed to extreme (say, big task 8 wo…

It depends what you're looking for. If you want someone who can turn the handle on your typical daily task then, sure, test them on your typical daily task. But if you want someone capable of developing solutions to brand new problems then it's not so easy and testing fundamental computer science theory is important.

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

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

#38

Post by Bancakes »

water8 wrote: post #2

The ratio of importance placed on these algorithm design in interviews vs the amount of times they actually come up in real world problems seems skewed IMO.

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.

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

#39

Post by globular-toast »

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

Earlier quoted context omitted.

It depends what you're looking for. If you want someone who can turn the handle on your typical daily task then, sure, test them on your typical daily task. But if you want someone capable of developing solutions to brand new problems then it's not so easy and testing fundamental computer science theory is important.

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 The Art of Computer Programming and The Art of Electronics on my shelf. I could find the sections to help sorting a list in seconds. As for the latter, I have no idea why the majority of that book even exists. I can't call myself an electrical engineer, even though all the theory I need is within arm's reach.

I assume you're arguing against the "recite the textbook" approach. I would agree that this is not the way to do things. But equally, "throw the textbooks out" is not the right way either. We need to evaluate a high-level grasp of the literature/theory but don't punish for forgetting minutiae. I might ask a candidate to talk about choice of sorting algorithms. There is, of course, no perfect answer, but what I'll be expecting is general evaluation of algorithms: time/memory tradeoffs, probing for more domain knowledge (e.g. does the data often come in sorted or random), platform constraints etc. I won't even expect a name drop of an actual sorting algorithm as that's not really the point. What they're telling me is they know why Knuth has a whole chapter on sorting. That's the important thing.

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

#40

Post by kryptiskt »

water8 wrote: post #2

The ratio of importance placed on these algorithm design in interviews vs the amount of times they actually come up in real world problems seems skewed IMO.

I disagree. There are so much code out there that nest loops and become accidentally quadratic, where a little knowledge would have helped make it perform well at scale. Knowledge about the time complexity of algorithms isn't valuable only for people implementing libraries. Every single time you iterate over things or partition things by a predicate you are using the building blocks of algorithms to make a new custom algorithm, and knowledge of the theory will help you avoid bad performance.

All nested loops are harbingers of algorithmic doom, and should be treated as such, and they come up all the time in real code.

Post reply on HN