Algorithms

Divide and Conquer

Цели урока

Understand the Divide & Conquer paradigm
Know the classic examples
Apply the Master Theorem
Solve problems using D&C

Предварительные знания

Merge Sort
Binary Search

'Divide and conquer' - the strategy used by Caesar and Napoleon. In algorithms it turns O(n²) into O(n log n) and O(n³) into O(n^2.81)!

Merge Sort, Quick Sort
FFT (Fast Fourier Transform)
Large number multiplication (Karatsuba)
Matrix multiplication (Strassen)

From von Neumann's merge sort to Karatsuba's multiplication

Divide and conquer is older than its name. In 1945 John von Neumann wrote down merge sort while working on the EDVAC, splitting an array in half, sorting each part, then merging. The most striking early result came in 1960. Andrey Kolmogorov had conjectured that multiplying two n-digit numbers required at least n squared operations. A 23-year-old student, Anatolii Karatsuba, broke that bound in a week: by rewriting the product with three multiplications instead of four, he reached roughly n raised to 1.585. Kolmogorov was so impressed he published the result under Karatsuba's name in 1962. The label divide and conquer itself spread later through Aho, Hopcroft and Ullman's 1974 textbook, which framed it as a general algorithm design technique alongside the Master Theorem for analyzing recurrences.

Idea: Divide and Conquer

**Divide and Conquer (D&C)** - one of the fundamental paradigms in algorithms. Three steps:

**When D&C is effective:**

The problem can be split into independent subproblems
Subproblems have the same structure as the original
Combining results is efficient
The recursion base case is trivial

**D&C vs Dynamic Programming:** in D&C subproblems are independent. In DP subproblems overlap (the same one is computed many times).

Binary Search is D&C. What is the COMBINE step?

Classic Examples

**1. Maximum subarray (D&C version of Kadane):**

**2. Fast exponentiation:**

**3. Karatsuba multiplication (large numbers):**

power(2, 1000) makes approximately how many multiplications?

Master Theorem

**Master Theorem** - a formula for analyzing D&C algorithms.

Algorithm	a	b	d	log_b(a)	T(n)
Binary Search	1	2	0	0	O(log n)
Merge Sort	2	2	1	1	O(n log n)
Karatsuba	3	2	1	1.58	O(n^1.58)
Strassen	7	2	2	2.81	O(n^2.81)

**Master Theorem is not universal!** It doesn't work for T(n) = T(n-1) + O(n) or when subproblems are of different sizes.

T(n) = 4T(n/2) + O(n). What is T(n)?

Practice: Closest Pair of Points

**Problem:** find the two closest points on a plane. Naive - O(n²). D&C - O(n log n)!

**The '7 points' trick:** in a strip of width d, for each point it's sufficient to check only ~7 neighbors by y. This makes COMBINE linear!

Why is it enough to check O(1) neighbors for each point in the strip?