This is a very important result in computer science. Check these slides or this video.
- Quick Select has bad theoretical worst-case running time. How can we find the median in linear time? Watch Turing Award winner Blum talk about his algorithm. Watch this explanation of the algorithm.
- Given a continuously arriving stream of data, how can we efficiently, at any point, report the median? Check these slides.
The following are more examples of well-known Divide & Conquer algorithms. Some of these examples were taught previousl at PSUT and are commonly taught in courses on algorithms.
-
Counting Inversions. This problem has many applications and can be solved efficiently with a slight modification of Mergesort. [video1][video2]
-
Karatsuba's Algorithm for Integer Multiplication. This is a classic (and quite clever) algorithm for multiplying two integers. It is better than the algorithms discussed in the introductory lecture of this course (slides from Spring 2023, video).
-
Finding the closest pair of points in a 2D space. While the divide and conquer algorithm is not the fastest known algorithm for this problem, it is a classic example of divide and conquer that can be eye opening to learn! [video]
-
Strassen's Algorithm for Matrix Multiplication (wikipedia article)