main page — CS 566 Efficient Algorithms
Unit 5: Divide & Conquer
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
- Master Theorem
- Median of Medians
- Karatsuba Multiplication
- MJRTY (Majority Element)
- Video 5-1 · transcript (2026-11-09, 16:30): Divide and Conquer recurrences
- Video 5-2 · transcript (2026-11-10, 34:43): The Master Theorem
- Video 5-3 · transcript (2026-11-10, 27:19): Selection by Rank, Quickselect
- Video 5-4 · transcript (2026-11-10, 12:39): Linear-Time Selection
- Video 5-5 · transcript (2026-11-10, 5:35): Long Multiplication
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.