THE MASTER METHOD- These lectures cover a "black-box" method for solving recurrences. You can then immediately determine the running time of most of the divide-and-conquer algorithms that you'll ever see! (Including Karatsuba's integer multiplication algorithm and Strassen's matrix multiplication algorithm from Week 1.) The proof is a nice generalization of the recursion tree method that we used to analyze MergeSort. Ever wonder about the mysterious three cases of the Master Method? Watch these videos and hopefully all will become clear.
QUICKSORT - THE ALGORITHM- One of the greatest algorithms ever, and our first example of a randomized algorithm. These lectures go over the pseudocode --- the high-level approach, how to partition an array around a pivot element in linear time with minimal extra storage, and the ramifications of different pivot choices --- and explain how the algorithm works.
QUICKSORT - THE ANALYSIS-These lectures are optional, but I strongly encourage you to watch them if you have time. They prove that randomized QuickSort (i.e., with random pivot choices) runs in O(n log n) time on average. The analysis is as elegant as the algorithm itself, and is based on a "decomposition principle" that is often useful in the analysis of randomized algorithms. Note that there are some accompanying lectures notes for this part (available for download underneath each video).
PROBABILITY REVIEW- This first of these optional lecture videos reviews the concepts from discrete probability that are necessary for the QuickSort analysis --- sample spaces, events, random variables, expectation, and linearity of expectation. The second video covers just two topics, although quite tricky ones! (Namely, conditional probability and independence.) You need to review this material (via this video or some other source, as you wish) before studying the analysis of the randomized contraction algorithm in Week 3.
HOMEWORK: Problem Set #2 has five questions that should give you practice with the Master Method and help you understand QuickSort more deeply. Programming Assignment #2 asks you to implement QuickSort and compute the number of comparisons that it makes for three different pivot rules.
RELATED READINGS: Algorithms Illuminated (Part 1), Chapters 4 and 5.
