4 ms·
MIT’s Introduction to Algorithms, Lecture 3: Divide and Conquer
- tristmegistus 18y agoFor the very interested the course website is http://ocw.mit.edu/OcwWeb/Electrical-Engineering-and-Computer-Science/6-046JFall-2005/CourseHome/index.htm 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 18y agoOh, the link is in the 1st post of the review series! Didn't feel like including it in every post. Perhaps I should.
- brent 18y agoThe 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 18y agoOops, sure, how to minimize area. I had these words in mind when I was writing the post. Fixed now. Thanks! :)
- aston 18y agoThe 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.