MIT’s Introduction to Algorithms, Lecture 3: Divide and Conquer

[ajbatac]

http://www.catonmat.net/blog/mit-introduction-to-algorithms-part-two/

[aston]

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.

[pkrumins → aston]

Thanks for your insightful comment! Can I use it in my post? (full credit to you)

[aston → pkrumins]

Yeah, definitely.

[tristmegistus]

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.

[pkrumins → tristmegistus]

Oh, the link is in the 1st post of the review series! Didn't feel like including it in every post. Perhaps I should.

[brent → pkrumins]

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".

[pkrumins → brent]

Oops, sure, how to minimize area. I had these words in mind when I was writing the post. Fixed now. Thanks! :)