News for hackers. Stuff that matters.
Re:MIT’s Introduction to Algorithms, Lecture 3: Divide and C... by aston on Thursday August 21, 2008 @07:17PM (#283286)
The killer concept to grok with divide-and-conquer is that it's only powerful if

  1) the smaller version of the problem is actually
     easier to solve and not just smaller
                  - or -
  2) the smaller version of the problem is just as 
     hard to solve, but you can combine smaller versions into
     a bigger one with less work than doing the bigger itself.
Quicksort is an example of the former (partitioning a list of size 2 or less is sorting it, even though partition is linear time). Merge sort is too (combining two sorted lists is linear time). Repeated squaring is an example of the latter, as is the Strassen matrix multiplication.

I took this class, and it took me a lot of just sitting around pondering before I got that stuff.

Re:MIT’s Introduction to Algorithms, Lecture 3: Divide and C... by pkrumins on Thursday August 21, 2008 @08:27PM (#283331)
Thanks for your insightful comment! Can I use it in my post? (full credit to you)
Re:MIT’s Introduction to Algorithms, Lecture 3: Divide and C... by aston on Thursday August 21, 2008 @08:50PM (#283346)
Yeah, definitely.