15.25 Exercises

You have learned the main divide-and-conquer patterns in this chapter.

algorithmsdivide-and-conquerrecursion

15.25 Exercises

Problem

You have learned the main divide-and-conquer patterns in this chapter. To make the techniques usable, you need practice turning a problem statement into:

split
recursive solution
combine
proof
complexity analysis
tests

This section gives a set of exercises designed to reinforce the chapter. Each exercise includes the intended pattern, expected complexity, and implementation hints. Treat these as recipes to complete, not as isolated puzzles.

Exercise 1: Implement Merge Sort with a Reusable Buffer

Write a merge sort implementation that allocates one temporary buffer and reuses it across all recursive calls.

Expected complexity:

$$ O(n\log n) $$

time and:

$$ O(n) $$

extra space.

Hints

Use index ranges:

func mergeSort(a, buf []int, lo, hi int)

Prefer half-open intervals:

[lo, hi)

because they make empty ranges and slice lengths easier to reason about.

Base case:

if hi-lo <= 1 {
    return
}

Merge into buf, then copy the result back into a.

Test Cases

[]
[1]
[2, 1]
[1, 1, 1]
[5, 4, 3, 2, 1]
[2, 4, 1, 3, 5]

Also test that the output is a permutation of the input.

Exercise 2: Add Stability to Merge Sort

Modify merge sort to sort records while preserving the relative order of records with equal keys.

Record:

type Record struct {
    Key int
    ID  string
}

Example input:

(2, "A")
(1, "X")
(2, "B")

Expected output:

(1, "X")
(2, "A")
(2, "B")

Hints

During merge, when keys are equal, take the element from the left half first.

if left.Key <= right.Key {
    take left
}

Correctness Requirement

Prove two properties:

  1. Output is sorted by key.
  2. Equal-key records retain original order.

Exercise 3: Implement Quickselect

Write a function:

func KthSmallest(nums []int, k int) int

where k is one-based.

Example:

nums = [9, 1, 6, 3, 8, 2, 7]
k = 3
answer = 3

Expected average complexity:

$$ O(n) $$

Expected worst case:

$$ O(n^2) $$

unless you add randomized pivots or median of medians.

Hints

Convert rank to index once:

target := k - 1

Use partitioning.

Recurse or iterate into only the side containing target.

Edge Cases

k = 1
k = len(nums)
duplicates
already sorted input
reverse sorted input

Exercise 4: Implement Three-Way Quickselect

Improve Quickselect for duplicate-heavy arrays.

Partition into:

< pivot
== pivot
> pivot

If the target index falls inside the equal region, return immediately.

Expected benefit:

[5, 5, 5, 5, 5]

should finish quickly.

Hints

Maintain three regions:

[low, lt)       < pivot
[lt, i)         == pivot
(i, gt]         unknown
(gt, high]      > pivot

This is the Dutch national flag partition pattern.

Exercise 5: Count Inversions

Implement:

func CountInversions(nums []int) int64

Use the merge-sort method.

Expected complexity:

$$ O(n\log n) $$

Hints

When merging sorted halves:

if left[i] > right[j]

then right[j] forms inversions with every remaining value in left.

Count:

mid - i

Use int64.

Test Against Brute Force

Write:

func CountInversionsBrute(nums []int) int64

and compare on many small random arrays.

Exercise 6: Count Reverse Pairs

Count pairs:

$$ i < j $$

such that:

$$ a[i] > 2a[j] $$

Expected complexity:

$$ O(n\log n) $$

Hints

Before merging, use two pointers:

j := mid

for i := lo; i < mid; i++ {
    for j < hi && a[i] > 2*a[j] {
        j++
    }

    count += j - mid
}

Then perform the normal merge.

Common Bug

Use a wider integer type when computing:

2 * a[j]

to avoid overflow.

Exercise 7: Binary Search on Answer

Solve the package shipping problem.

Given package weights and a number of days, find the minimum ship capacity.

Example:

weights = [3, 2, 2, 4, 1, 4]
days = 3
answer = 6

Hints

Lower bound:

max(weights)

Upper bound:

sum(weights)

Feasibility test:

can ship within days using capacity C

Expected complexity:

$$ O(n\log S) $$

where (S) is the sum of weights.

Exercise 8: Router Placement

Given sorted house positions and an integer k, place k routers to maximize the minimum distance between any two routers.

Example:

positions = [1, 2, 8, 12, 17]
k = 3
answer = 7

One placement:

1, 8, 17

Minimum distance:

7

Hints

Binary search the distance.

Feasibility test:

greedily place routers from left to right

If distance d is feasible, smaller distances are also feasible.

Search for the largest feasible distance.

Exercise 9: Fast Exponentiation

Implement:

func Pow(x int64, n int64) int64

for nonnegative exponents.

Then implement:

func ModPow(x, n, mod int64) int64

Expected complexity:

$$ O(\log n) $$

Hints

Use the iterative method.

Loop invariant:

result * base^exp == original x^original n

For ModPow, reduce after each multiplication.

Exercise 10: Matrix Exponentiation for Fibonacci

Use fast exponentiation on the matrix:

$$ \begin{bmatrix} 1 & 1 \\n1 & 0 \end{bmatrix} $$

to compute Fibonacci numbers.

Expected complexity:

$$ O(\log n) $$

matrix multiplications.

Hints

Define a 2-by-2 matrix type.

Implement:

func Mul(a, b Matrix) Matrix
func PowMatrix(a Matrix, n int64) Matrix

Then use the known relationship between matrix powers and Fibonacci numbers.

Exercise 11: Karatsuba Multiplication for Strings

Implement Karatsuba multiplication for nonnegative integers represented as decimal strings.

Example:

"1234" * "5678" = "7006652"

Hints

You need helpers for:

string addition
string subtraction
shifting by powers of 10
trimming leading zeros

Use grade-school multiplication below a small threshold.

Correctness Checks

Compare against a big-integer library for random inputs.

Exercise 12: Closest Pair by Brute Force and Divide and Conquer

Implement both versions.

func ClosestPairBrute(points []Point) float64
func ClosestPair(points []Point) float64

Compare their results on small random point sets.

Expected optimized complexity:

$$ O(n\log n) $$

Hints

Use squared distance internally.

Sort once by x-coordinate and y-coordinate.

Handle duplicate points.

For small subproblems, use brute force.

Exercise 13: Merge-Sort Tree

Build a merge-sort tree that answers:

count values <= x in range [l, r]

Expected complexity:

build: O(n log n)
query: O(log² n)

Hints

Each segment tree node stores a sorted slice.

Queries decompose the target range into segment tree nodes.

Use upperBound inside each covered node.

Exercise 14: Offline Dynamic Connectivity

Given operations:

add edge
remove edge
ask connected(u, v)

process all queries offline.

Expected technique:

segment tree over time
rollback union-find

Hints

Each edge is active over one or more time intervals.

Add the edge to segment tree nodes covering those intervals.

DFS over the tree.

Apply unions when entering a node.

Rollback when leaving.

Avoid path compression in rollback union-find.

Exercise 15: FFT-Based Polynomial Multiplication

Implement polynomial multiplication using FFT.

Input:

A coefficients
B coefficients

Output:

C coefficients

Expected complexity:

$$ O(n\log n) $$

Hints

Pad to the next power of two at least:

len(A) + len(B) - 1

Use inverse FFT.

Round real parts when output should be integral.

Test against quadratic multiplication on small random inputs.

Exercise 16: Parallel Merge Sort

Implement parallel merge sort with two cutoffs:

minimum size
maximum depth

Expected behavior:

  • faster than sequential for large arrays
  • not slower for small arrays
  • no unbounded goroutine creation

Hints

Spawn one recursive branch.

Run the other branch locally.

Wait before merging.

Benchmark different thresholds.

Exercise 17: Cache-Oblivious Matrix Transpose

Implement recursive matrix transpose over a flat row-major array.

Expected benefit:

better locality than naive column writes

for large matrices.

Hints

Split along the larger dimension.

Use an iterative base kernel for small blocks.

Benchmark against the naive implementation.

Exercise 18: Prove Merge Sort Correctness

Write a proof in plain English.

Your proof must show:

  1. Termination
  2. Sortedness
  3. Preservation of elements

Suggested Structure

Use induction on array length.

Prove a helper lemma:

Merge of two sorted arrays is sorted and preserves elements.

Then use the lemma in the recursive proof.

Exercise 19: Analyze Quick Sort Worst Case

Show that if the pivot is always the smallest element, the recurrence is:

$$ T(n)=T(n-1)+O(n) $$

Then expand it to prove:

$$ T(n)=O(n^2) $$

Extra Task

Explain why random pivot selection changes the expected behavior.

Exercise 20: Design Your Own Divide-and-Conquer Algorithm

Choose one problem:

range aggregation
log analysis
top-k extraction
geometric filtering
time-series segmentation
large file processing

Write:

  1. Problem statement
  2. Brute-force solution
  3. Recursive split
  4. Combine step
  5. Correctness argument
  6. Complexity analysis
  7. Test strategy

This exercise forces you to apply the chapter pattern outside textbook examples.

Review Questions

  1. What must be true for binary search on answer to work?
  2. Why does Quickselect recurse into only one side?
  3. Why does merge sort require (O(n)) auxiliary memory in typical implementations?
  4. What makes median of medians worst-case linear?
  5. Why can closest-pair strip processing be linear?
  6. What is the difference between cache-aware and cache-oblivious algorithms?
  7. When is offline query processing preferable to online processing?
  8. Why is testing helper invariants useful?
  9. Why does Karatsuba improve over grade-school multiplication?
  10. What information does a recurrence omit about real performance?

Closing Notes

Divide and conquer becomes practical through repetition. The split is usually easy to see after some practice. The combine step is where the algorithm either succeeds or fails.

For every exercise, write the brute-force version first. Then write the optimized version. Test them against each other on small inputs. Finally, analyze the recurrence and benchmark the implementation.

This process keeps the algorithm honest. It connects design, proof, testing, and performance into one workflow.