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.
Re:MIT’s Introduction to Algorithms, Lecture 3: Divide and C... by tristmegistus on Thursday August 21, 2008 @06:09PM (#283220)
For the very interested the course website is http://ocw.mit.edu/OcwWeb/Electrical-Engineering-and-Compute.... It has the videos, lecture notes, problems sets and solutions. I missed the link on Peteris' review.
Re:MIT’s Introduction to Algorithms, Lecture 3: Divide and C... by pkrumins on Thursday August 21, 2008 @06:20PM (#283226)
Oh, the link is in the 1st post of the review series! Didn't feel like including it in every post. Perhaps I should.
Re:MIT’s Introduction to Algorithms, Lecture 3: Divide and C... by brent on Thursday August 21, 2008 @07:21PM (#283289)
The last topic covered in this lecture is VLSI (Very large Scale Integration) layout problem: given a number of various electronic gates an chips, how to position them on the circuit board.

You may want to state the objective here as well. I haven't seen the lecture, but from the still on the google video I presume it is "... how to position them to minimize area".

Re:MIT’s Introduction to Algorithms, Lecture 3: Divide and C... by pkrumins on Thursday August 21, 2008 @07:53PM (#283313)
Oops, sure, how to minimize area. I had these words in mind when I was writing the post. Fixed now. Thanks! :)