main page — CS 566 Efficient Algorithms
Unit 5: Divide & Conquer
This is an archived version of this module from Winter 2024-25.
This unit covers
- the divide & conquer design paradigm
- analysis techniques, Master Theorems
- quickselect
- median of medians algorithm
- Karatsuba multiplication
- majority algorithms
- closest pair of points
Learning outcomes
- Know the steps of the Divide & Conquer paradigm.
- Be able to solve simple Divide & Conquer recurrences.
- Be able to design and analyze new algorithms using the Divide & Conquer paradigm.
- Know the performance characteristics of selection-by-rank algorithms.
- Know the divide and conquer approaches for integer multiplication, matrix multiplication, finding majority elements, and the closest-pair-of-points problem.
Material
- slides
- Video 5-1 (2024-11-11):
§5.1 Divide & Conquer recurrences, Master Theorem
- Video 5-2 (2024-11-11):
§5.2 Order statistics, quickselect
- Video 5-3 (2024-11-12):
§5.3 Linear-time selection, median of medians
- Video 5-4 (2024-11-12):
§5.4 Fast multiplication: Karatsuba and Strassen
- Video 5-5 (2024-11-12):
§5.5 Majority: divide and conquer, Boyer-Moore MJRTY
- Video 5-6 (2024-11-18):
§5.6 Closest pair of points in the plane
Further reading and sources
The presentation of quickselect and the median-of-medians algorithm is inspired by material prepared for the module
Fast multiplication follows the presentation our book
The Master Method discussion takes inspiration from
- Cormen, Leiserson, Rivest, Stein: Introduction to Algorithms 4th ed (2022), MIT Press
Note that the section on the master method has been substantially changed in the 4th edition
Further details on divide-and-conquer recurrences can be found in
- Kuszmaul, Leiserson: Floors and Ceilings in Divide-and-Conquer Recurrences, SOSA 2021
- Roura: Improved master theorems for divide-and-conquer recurrences, Journal of the ACM, 2001
The closest pair of points problem is discussed in
- Cormen, Leiserson, Rivest, Stein: Introduction to Algorithms 3rd ed (2009), MIT Press
Note that here, the 4th edition has this chapter removed.