Lecture 2: Divide & Conquer: Convex Hull, Median Finding

What this lecture covers

This lecture opens the divide-and-conquer module with two problems chosen because the technique's difficulty lands in different places for each. Convex hull is easy to divide but requires a clever merge step; median finding is easy to merge but requires a clever, carefully balanced division step.

By the end, you can describe the general divide-and-conquer recurrence T(n) = a*T(n/b) + [merge work], explain the two-finger algorithm for merging two convex hulls in linear time to get an overall Theta(n log n) hull algorithm, and describe the median-of-medians technique that picks a pivot guaranteeing balanced partitions, giving a deterministic Theta(n) selection algorithm.

Key ideas

• Divide-and-conquer recurrence: a problem of size n splits into a subproblems of size n/b, solved recursively, then combined; complexity depends on how expensive the combine step is.
• Convex hull: the smallest polygon enclosing a set of 2D points, represented as points in clockwise order around the boundary.
• Brute-force hull: testing every pair of points as a candidate edge and checking whether all other points lie on one side takes Theta(n^3).
• Two-finger merge: given two convex hulls split by x-coordinate, the upper (and lower) tangent connecting them can be found in Theta(n) by walking two pointers, one clockwise and one counterclockwise, until the connecting segment's intercept stops increasing.
• Cut and paste: once the upper and lower tangents are known, splicing the two hulls into one circular list is a Theta(n) walk that drops the now-interior points.
• Rank and median: rank(x) counts elements <= x; the median is the element of rank floor((n+1)/2).
• Naive pivot selection fails: picking an arbitrary or fixed-index pivot for the select algorithm can produce unbalanced partitions and Theta(n^2) worst-case time.
• Median of medians: splitting the array into groups of five, sorting each group, and recursively finding the median of the group medians produces a pivot that guarantees at least roughly 3n/10 elements fall on each side, giving the recurrence T(n) = T(n/5) + T(7n/10) + Theta(n), which solves to Theta(n).

Walkthrough

The divide-and-conquer paradigm (2:01)

Devadas generalizes merge sort's pattern: divide a size-n problem into a subproblems of size n/b, solve each recursively down to a small base case, then combine. He notes that for most examples in the course, including both problems in this lecture, the division step is simple and the real difficulty is in the combine (merge) step.

Defining convex hull (6:04)

Using a physical prop, Devadas defines the convex hull of a set of 2D points (no two sharing an x or y coordinate, no three collinear) as the smallest enclosing polygon, represented as a clockwise doubly linked list of boundary points. He shows the brute-force algorithm: for every pair of points, draw the line through them and check whether all remaining points lie on one side; this takes Theta(n) per test over Theta(n^2) pairs, giving Theta(n^3) overall.

Dividing and merging two hulls with two fingers (20:25)

Points are sorted once by x-coordinate and split into a left half and right half, each solved recursively (falling back to brute force at small sizes). The interesting part is merging two convex hulls, since checking every pair of points across the two hulls would cost Theta(n^2). The two-finger algorithm instead starts one pointer at the rightmost point of the left hull and another at the leftmost point of the right hull, then alternately moves each pointer (one clockwise, one counterclockwise) as long as doing so increases the y-intercept of the connecting segment, converging on the upper tangent in Theta(n). The same idea, run for decreasing intercepts, finds the lower tangent.

Splicing the hulls and the resulting recurrence (46:00)

Once the upper and lower tangents are found, a cut-and-paste step walks from the upper tangent's endpoint around one hull to the lower tangent's endpoint, then around the other hull back to the start, discarding points that are no longer on the boundary. This step is Theta(n). Combined with the sorted division, the overall recurrence is T(n) = 2T(n/2) + Theta(n), the same form as merge sort, giving Theta(n log n) total, which the lecture notes is optimal for the general convex hull problem.

Median finding by rank selection (52:07)

The goal shifts to finding the element of a given rank (the median being a special case) in better than Theta(n log n) time. The select(S, i) routine picks a pivot x, computes its rank k, partitions the remaining elements into B (less than x) and C (greater than x), and recurses into whichever side contains the desired rank, adjusting the target rank when recursing into C. Devadas shows that if the pivot is chosen carelessly (an extreme value, or always the middle index), the partitions can be maximally unbalanced, giving Theta(n^2) worst-case time.

Median of medians for a deterministic linear-time pivot (1:04:26)

To guarantee balance deterministically, the algorithm arranges the array into columns of five, sorts each column in constant time, and recursively finds the median of the n/5 column medians as the pivot x. Because roughly half the columns have their median above x and half below, and each such column contributes at least three elements on its side, at least around 3n/10 elements are guaranteed to be greater than x and at least around 3n/10 less than x. This yields the recurrence T(n) = T(n/5) + T(7n/10) + Theta(n) for n above a constant base case; since n/5 + 7n/10 < n, the recurrence solves to Theta(n), an algorithm that finds any rank, including the median, in linear time.

Before you watch

• Be comfortable with the merge sort divide-and-conquer recurrence and how to reason about it informally.
• Review basic recurrence notation (T(n) = a*T(n/b) + f(n)); the lecture references the master theorem, covered separately in section.
• Watching Lecture 1 first helps, since this lecture assumes familiarity with the course's general approach to proving algorithm correctness and complexity.

Check your understanding

1. Why does the brute-force convex hull algorithm take Theta(n^3) time, and which step does divide and conquer improve?
2. Explain why the two-finger algorithm is guaranteed to find the correct upper tangent in Theta(n) time rather than needing to check every pair of points.
3. What goes wrong with the select algorithm's worst-case running time if the pivot is always chosen to be the smallest or largest remaining element?
4. Why does splitting the array into groups of five, rather than some other constant group size, matter for the median-of-medians argument?
5. How does the recurrence T(n) = T(n/5) + T(7n/10) + Theta(n) lead to a linear-time bound, given that the two recursive terms don't sum to n?