ConceptSystems & CS
Divide and conquer algorithm
Splitting a problem into smaller sub-problems recursively until they can be solved directly, then merging the sub-solutions together.
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.
Recursion1Sub-problems1
Opens up
Concepts that name this one as a prerequisite.
Fast Fourier transform3Cache-oblivious algorithm1Cache-oblivious matrix multiplication (divide and conquer)1Cache-oblivious stencil computation1Coarsening1Discrete Fourier transform (DFT) method1Divide and conquer matrix multiplication1Karatsuba algorithm1Karatsuba algorithm time complexity1Karatsuba multiplication1Quicksort specification1Recurrence relation for median finding1
Lecturers
1Lectures that assume it
15The first 12 are shown.
- Introduction and Matrix Multiplication
- Divide & Conquer: FFT
- Parallel Storage Allocation
- Cache-Oblivious Algorithms
- Cache-Oblivious Algorithms: Medians and Matrices
- Integer Arithmetic, Karatsuba Multiplication
- Divide & Conquer: Convex Hull, Median Finding
- Thinking Above the Code
- Complexity of Basic Arithmetic
- Strings
- Analysis of Multithreaded Algorithms
- Side-Channel Attacks
Connections
22The lectures that define it or assume it, and the concepts next to it.
Concepts6
Lectures16
- Introduction to Parallel Programming with OpenMP (Part 3)
- Introduction and Matrix Multiplication
- Divide & Conquer: FFT
- Parallel Storage Allocation
- Cache-Oblivious Algorithms
- Cache-Oblivious Algorithms: Medians and Matrices
Show 10 moreShow fewer
- Integer Arithmetic, Karatsuba Multiplication
- Divide & Conquer: Convex Hull, Median Finding
- Thinking Above the Code
- Complexity of Basic Arithmetic
- Strings
- Analysis of Multithreaded Algorithms
- Side-Channel Attacks
- Efficient Fine-Grained Algorithms
- Fast Fourier Transform (FFT) and Integer Multiplication
- Rotate, Compute, Rotate