ConceptTheory & Algos
Divide and conquer
An algorithmic paradigm that breaks a problem into smaller subproblems of the same type, solves them recursively, and combines their results.
Know first
Named as a prerequisite by the lectures that define this. The number is how many say so. A grey one has no page yet.
Opens up
Concepts that name this one as a prerequisite.
Binary search2Median finding2Basic Quicksort1Batched orthogonal range searching1Binary merger via upward sweep1Binary search tree1Complexity of convex hull merge1Distribution sweep1Divide and conquer in cache-oblivious algorithms1High precision multiplication1Median finding in cache-oblivious model1Merge sort1
Lecturers
5Each in their own terms, from the easiest level.
Erik Demaine & Srini Devadas
David J. Malan
An algorithmic strategy that breaks a problem into smaller sub-problems, solves them, and combines the results.Julian Shun
An algorithmic paradigm that solves a problem by recursively breaking it down into smaller sub-problems of the same type.Srini Devadas
A strategy that recursively breaks a problem down into smaller sub-arrays to solve it efficiently.Clive Stafford Smith
A political strategy of gaining and maintaining power by breaking up larger concentrations of power into chunks that individually have less power, such as stirring up hatred toward specific groups.
Lectures that assume it
8- Binary Search Trees & Runway Reservation Scheduling
- Insertion Sort, Binary Insertion & Merge Sort Recurrences
- Randomization: Matrix Multiply, Quicksort
- Cache-Oblivious Algorithms: Medians and Matrices
- Integer Arithmetic, Karatsuba Multiplication
- Square Roots, Newton's Method
- Cache-Oblivious Algorithms: Searching & Sorting
- Cache-Oblivious Structures II
Connections
23The lectures that define it or assume it, and the concepts next to it.
Concepts7
Show 1 moreShow fewer
Lectures16
- Course Overview, Interval Scheduling
- Divide & Conquer: FFT
- Caching and Cache-Efficient Algorithms
- Algorithmic Thinking & Peak Finding in 1D and 2D
- Divide & Conquer: Convex Hull, Median Finding
- Algorithms
Show 10 moreShow fewer
- Data Structures
- Give Peace a Chance: Legal Implications of the Israel-Palestine Conflict
- Binary Search Trees & Runway Reservation Scheduling
- Insertion Sort, Binary Insertion & Merge Sort Recurrences
- Randomization: Matrix Multiply, Quicksort
- Cache-Oblivious Algorithms: Medians and Matrices
- Integer Arithmetic, Karatsuba Multiplication
- Square Roots, Newton's Method
- Cache-Oblivious Algorithms: Searching & Sorting
- Cache-Oblivious Structures II