Chapter 15: Divide and Conquer. 25 sections.
25 items
You are given a recursive algorithm and want to determine its time complexity.
Many divide-and-conquer algorithms produce recurrences of the form \[ T(n)=aT\left(\frac{n}{b}\right)+f(n) \]
You need to sort a collection of elements efficiently while preserving the relative order of equal values.
Merge sort guarantees \(O(n \log n)\) performance and stable ordering, but it requires additional memory proportional to the input size.
Given \(n\) points on a two-dimensional plane, find the pair of points whose Euclidean distance is minimal.
You need to multiply very large integers.
Karatsuba's algorithm demonstrates that multiplication can be accelerated by reducing the number of recursive subproblems.
You need to compute: \[ x^n \]
Many dynamic programming algorithms compute a table with the recurrence: \[ dp[i] = \min_{j < i} \left(dp[j] + cost(j,i)\right) \]
Divide-and-conquer algorithms naturally create independent subproblems.
An algorithm can have good asymptotic complexity and still run poorly on real hardware.
You need to find the \(k\)-th smallest element in an unsorted array.
Quickselect finds the \(k\)-th smallest element in expected linear time.
You need to measure how far an array is from being sorted.
Some problems ask for an optimal value rather than a specific object.
You need to multiply two polynomials.
You need to answer many queries over a fixed dataset.
Given \(n\) points in a plane, find the pair with the smallest Euclidean distance.
A divide-and-conquer algorithm may look correct because its structure is simple: ```text split solve recursively
You have a divide-and-conquer algorithm and need to analyze its running time and memory usage.
Divide-and-conquer algorithms are prone to subtle implementation errors.
Divide-and-conquer algorithms often fail in ways that are difficult to see from the high-level design.
After studying many divide-and-conquer algorithms, they can appear unrelated.
You have learned the mechanics of divide and conquer: ```text split solve recursively
You have learned the main divide-and-conquer patterns in this chapter.