4 ms·

What would be an example of a successful application of this approach?

jacquesm 16y ago
When faced with a problem too large to solve divide it in to two roughly equal halves. Pick the first half of the two and see if you can solve it. If not recurse with the first half, else solve it. Now look at the other half and see if you can solve it. if not recurse with the second half, otherwise solve it. For debugging it mostly relates to chopping up the program in to bits that are 'verified good' and 'unsure', until you are literally staring at the bug. Some sort/search algorithms are an almost literal implementation of divide-and-conquer. edit: the more I think about this the more I realize that this has pervaded in to just about everything that I do. I'm currently rebuilding a car that has crashed and I find I use divide and conquer to troubleshoot and to repair. Tomorrow I'll be puling the engine to replace a cracked gearbox casing and for sure I'll use it again, both to remove the engine, to remove and replace the gearbox and to put the whole thing back together again, one small 'obvious' step at a time. edit2: see also: http://news.ycombinator.com/item?id=1695794 http://news.ycombinator.com/item?id=1695794
- varjag 16y ago
  > For debugging it mostly relates to chopping up the program in to bits that are 'verified good' and 'unsure', until you are literally staring at the bug. It should be noted there's a whole class of bugs where divide and conquer simply doesn't work. E.g. about anything with race condition. Good points otherwise.
  - jacquesm 16y ago
    True enough, and interrupt driven programs tend to exhibit very nasty ones as well where that strategy does not work. It's not a 100% silver bullet but it will get you quite far.
  - deleted 16y ago
    [deleted]
  - deleted 16y ago
    [deleted]
- achompas 16y ago
  Excellent suggestion. This open course lecture from MIT has more, for those who want an example or two: http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-00-introduction-to-computer-science-and-programming-fall-2008/lecture-videos/embed10/ http://ocw.mit.edu/courses/electrical-engineering-and-comput...
brown9-2 16y ago
MapReduce

When faced with a problem too large to solve divide it in to two roughly equal halves. Pick the first half of the two and see if you can solve it. If not recurse with the first half, else solve it. Now look at the other half and see if you can solve it. if not recurse with the second half, otherwise solve it. For debugging it mostly relates to chopping up the program in to bits that are 'verified good' and 'unsure', until you are literally staring at the bug. Some sort/search algorithms are an almost literal implementation of divide-and-conquer. edit: the more I think about this the more I realize that this has pervaded in to just about everything that I do. I'm currently rebuilding a car that has crashed and I find I use divide and conquer to troubleshoot and to repair. Tomorrow I'll be puling the engine to replace a cracked gearbox casing and for sure I'll use it again, both to remove the engine, to remove and replace the gearbox and to put the whole thing back together again, one small 'obvious' step at a time. edit2: see also: http://news.ycombinator.com/item?id=1695794 http://news.ycombinator.com/item?id=1695794

varjag 16y ago
> For debugging it mostly relates to chopping up the program in to bits that are 'verified good' and 'unsure', until you are literally staring at the bug. It should be noted there's a whole class of bugs where divide and conquer simply doesn't work. E.g. about anything with race condition. Good points otherwise.
- jacquesm 16y ago
  True enough, and interrupt driven programs tend to exhibit very nasty ones as well where that strategy does not work. It's not a 100% silver bullet but it will get you quite far.
- deleted 16y ago
  [deleted]
- deleted 16y ago
  [deleted]
achompas 16y ago
Excellent suggestion. This open course lecture from MIT has more, for those who want an example or two: http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-00-introduction-to-computer-science-and-programming-fall-2008/lecture-videos/embed10/ http://ocw.mit.edu/courses/electrical-engineering-and-comput...

brown9-2 16y ago

MapReduce