Divide-and-conquer Paradigm

Divide-and-conquer is to

• divide up problem into several subproblems of the same kind
• solve (conquer) each subproblem recursively
• combine solutions to subproblems into overall solution

Most common usage

• divide problem of size $n$ into two subproblems of size $n/2$. (this takes $O(n)$ time).
• solve (conquer) two subproblems recursively
• combine two solutions into overall solution (takes $O(n)$ time)

Consequence: brute force method may take $\Theta(n^2)$ and divide-and-conquer takes $O(n\log n)$.

Mergesort

Problem: give a list $L$ of $n$ elements from a totally ordered universe, rearrange them in ascending order.

Solution:

• recrusively sort the left half
• recursively sort the right half
• merge two halves to make sorted whole.

Merging

Goal: combine two sorted lists $A$ and $B$ into a sorted whole $C$.

• scan $A$ and $B$ from left to right
• compare $a_i$ and $b_j$
  • if $a_i \leq b_j$, append $a_i$ to $C$ (no larger than any remaining element in $B$).
  • if $a_i > b_j$, append $b_j$ to $C$ (smaller than every remaining element in $A$).

Implementation

Input: list $L$ of $n$ elements from a totally ordered universe Output: the $n$ elements in ascending order

Merge-Sort(L) If (list $L$ has one element)

• return $L$

Divide the list into two halves $A$ and $B$

• $A \leftarrow$ Merge-Sort($A$) (this will take $T(n/2)$)
• $B \leftarrow$ Merge-Sort($B$) (this will take $T(n/2)$)
• $L \leftarrow$ Merge($A$, $B$)

Return $L$

Analysis

A useful recurrence relation: Definition: $T(n) =$ max number of compares to mergesort a list of length $n$

Recurrence:

\left\{ \begin{array}{lr} 0, & \text{if } n = 1\\ T(\lfloor n/2 \rfloor) + T(\lceil n/2 \rceil) + n, & \text{if } n > 1 \end{array} \right\}$$ - The $n$ is the complexity of the merge operation and it comes from between $\lfloor n/2 \rfloor$ and $n-1$ compares. Solution: $T(n)$ is $O(n \log_2 n)$. Assorted proofs: we describe several ways to solve this recurrence. Initially we assume $n$ is a power of $2$ and replace $\leq$ with $=$ in the recurrence. ## Recursion Tree Proposition: if $T(n)$ satisfies the following recurrence, then $T(n) = n \log_2 n$ (assuming $n$ is a power of $2$). $$T(n) \leq \left\{ \begin{array}{lr} 0, & \text{if } n = 1\\ 2T(n/2) + n, & \text{if } n > 1 \end{array} \right\}$$ The tree will have a depth of $\log_2 n$ *Proof by induction* Proposition: if $T(n)$ satisfies the following recurrence, then $T(n) = n \log_2 n$ and the above is true. Proof [by induction on $n$]: - Base case: when $n=1$, $T(1) = 0 = n \log_2 n$. - Inductive hypothesis: assume $T(n) = n \log_2 n$. - Goal: show that $T(2n) = 2n log_2 (2n)$.

\begin{align}
T(2n) &= 2 T(n) + 2n \&= 2n\log_2 n + 2n \&= 2n(\log_2 (2n) - 1) + 2n \&= 2n\log_2 (2n) \end{align}

Analysis of mergesort recurrence. Proposition: if $T(n)$ satisfies the following recurrence, then $T(n) \leq n \lceil \log_2 n \rceil$ $$T(n) \leq \left\{ \begin{array}{lr} 0, & \text{if } n = 1\\ T(\lfloor n/2 \rfloor ) + T(\lceil n/2 \rceil) + n, & \text{if } n > 1 \end{array} \right\}$$ Proof: by strong induction on $n$. - base case: $n=1$ - define $n_1 = \lfloor n/2 \rfloor$ and $n_2 = \lceil n/2 \rceil$ and note that $n = n_1 + n_2$. - induction step: assume true for $1, 2,\cdots, n-1$

\begin{align}
T(n) &\leq T(n_1) + T(n_2) + n \&\leq n_1 \lceil \log_2 n_1 \rceil + n_2 \lceil \log_2 n_2 \rceil + n \&\leq n_1 \lceil \log_2 n_2 \rceil + n_2 \lceil \log_2 n_2 \rceil + n \&= n \lceil \log_2 n_2 \rceil + n \&\leq n(\lceil \log_2 n \rceil - 1) + n \&= n \lceil \log_2 n\rceil \end{align}

- second line is the inductive hypothesis - we know that $\log_2 n_2 \leq \lceil \log_2 n \rceil -1$ ## Digression: sorting lower bound How can we prove a lower bound for *all* conceivable algorithms? - can't do better than a certain amount for all sorting algorithms. Model of computation: comparison trees - can access the elements only through pairwise comparisons - all other operations (control, data movement, etc.) are free. Cost model: number of compares is n! (where n is the number of variables we are comparing). *Theorem*: any deterministic compare-based sorting algorithm must take $\Omega(n \log n)$ compares in the worst-case. *Proof* by [information theoretics] - assume array consists of $n$ distinct values $a_1$ through $a_n$ - worst-case numbers of compares = height $h$ of pruned comparison tree - binary tree of height $h$ has $\leq 2^h$ elaves - $n!$ different orderings $\Rightarrow n!$ reachable leaves.

\begin{align}
2^h \geq \text{# of leaves} \geq n! \ \Rightarrow h &\geq \log_2(n!) \ &\geq n \log_2 n - n \ \ln 2 \end{align}

# Counting Inversions Example of counting inversions: music site tries to match your song preference to others. - you rank $n$ songs - music site consults database to find people with similar tastes *Similarity metric:* number of *inversions* between two rankings - my rank: $1, 2, \dots, n$ - your rank: $a_1, a_2, \dots, a_n$ - songs $i$ and $j$ are inverted if $i < j$, but $a_i > a_j$. *Brute force*: check all $\Theta(n^2)$ pairs. Apply divide and conquer: - divide: separate list into two halves $A$ and $B$. - conquer: recursively count inversions in each list - combine: count inversions $(a,b)$ with $a \in A$ and $b \in B$. - Return the sum of the three counts. How do you combine two subproblems? I.e., how do you could the inversions $(a,b)$ with $a \in A$ and $b \in B$ assuming that $A$ and $B$ are sorted. - scan $A$ and $B$ from left to right - compare $a_i$ and $b_j$ - If $a_i < b_j$, then $a_i$ is not inverted with any element left in $B$. - If $a_i > b_j$, then $b_j$ is inverted with every element left in $A$. - Append the smaller element to sorted list $C$. The algorithm ``` Merge-and-Count(A,B) Maintain a Current pointer into each list, initialized to point to the front elements Maintain a variable Count for the number of inversions, initialized to 0. While both lists are nonempty: Let ai and bj be the elements pointed to by the Current pointer. Append the smaller of these two to the output list If bj is the smaller element then Increment Count by the number of elements remaining in A Endif Advance the Current pointer in the list from which the smaller element was selected. EndWhile Once one list is empty, append the remainder of the other list to the ouptut. Return Count and the merged lsit ``` Counting inversions: divide-and-conquer algorithm implementation Input: list L Output: number of inversions in L and L in sorted order Sort-and-count(L): - If (list $L$ has one elment) - Return $(0,L)$ - Divide the list into two halves: $A$ and $B$. - $(r_A, A) \leftarrow$ Sort-and-count($A$). // $T(n/2)$ - $(r_b, B) \leftarrow$ Sort-and-count($B$). // $T(n/2)$ - $(r_{AB}, L) \leftarrow$ Sort-and-count($A,B$). // $\Theta(n)$ - Return $(r_a + r_b + r_{AB}, L)$ Counting inversions: divide-and-conquer algorithm analysis. - Proposition: the sort-and-count algorithm counts the number of inversions in a permutation of size $n$ in $O(n\log n)$ time. - Proof: the worst-case running time $T(n)$ satisfies the recurrence $$T(n) \leq \left\{ \begin{array}{lr} \Theta (1), & \text{if } n = 1\\ T(\lfloor n/2 \rfloor ) + T(\lceil n/2 \rceil) + \Theta(n), & \text{if } n > 1 \end{array} \right\}$$ # Randomized Quicksort - Pick a random pivot element $p \in A$ - 3-way partition the array into $L$, $M$, and $R$ - Recursively sort both $L$ and $R$. Randomized-Quicksort$(A$): - If (array $A$ has zero or one element) - Return - Pick pivot $p \in A$ uniformly at random - $(L, M, R) \leftarrow$ Partition-3-way ($A, p$) // $\Theta(n)$ - Randomized-Quicksort(L) // $T(i)$ - Randomized-Quicksort(R) // $T(n-i-1)$ new analysis required because $i$ is a random variable that depends on $p$. ## Analysis Proposition: the expected number of compares to quicksort an array of $n$ distinct elements $a_1 < a_2 < \dots < a_n$ is $O(n\log n)$ Proof: consider teh BST representeation of pivot elements. This is when the nodes are the pivot chosen. E.g., parent node is the first pivot, and its left leaf is the first pivot in its left subarray. - $a_i$ and $a_j$ are compared once iff one is an ancestor of the other. - Pr[$a_i$ and $a_j$ are compared] = $2/(j-i+1)$ where $i < j$. - The exepcted number of compares becomes the sum of all pairs $i$ and $j$ = $$\sum^{n}_{i=j}\sum^{n}_{j=i+1} \frac{2}{j-i+1}= 2\sum^{n}_{i=1}\sum^{n-i+1}_{j=2}\frac{1}{j} \leq 2n \sum^{n}_{j=1}\frac{1}{j} \leq 2n(\ln n + 1)$$ where the equality is true because of harmonic sum. Tony Hoare was the inventor of quicksort. Made to translate russian to english. # Closest Pair of Points Closest pair problem: given $n$ points in the plane, find a pair of points with the smallest Euclidean distance between them. Brute force solution: check all pairs with $\Theta (n^2)$ distance calculations In 1D: an least $O(n \log n)$ algorithm can solve it if the points are on a line. Non-degeneracy assumption: no two points has the same $x-coordinate$ The divide-and-conquer algorithm: - divide: draw a vertical line $L$ so that $n/2$ poitns on each side. - conquer: find closest pair in each side recursively - combine: find closest pair with one point in each side (seems like $\Theta(n^2)$) - return the best of the three solutions How do you find the closest pair with one point in each side? Assume the distance $< \delta$ where $\delta$ is the minimum between the distances of the closest pairs of the right and left side. - observation: it suffices to consider only those points within $\delta$ of line $L$. - sort points in $2\delta$-strip by their y-coordinate - check if distances of only those points within 7 positions of the list. Let's see why 7. Definition: let $s_i$ be the point in the $2\delta$-strip, with the $i$th smallest y-coordinate. Claim: if $|j-i| > 7$ then the distance between $s_i$ and $s_j$ is at least $\delta$. Proof: - consider the $2\delta$-by-$\delta$ rectangle $R$ in the strip whose min y-coordinate is y-coordinate of $s_i$. - distance between $s_i$ and any point $s_j$ above $R$ is $\geq\delta$. - Subdivide $R$ into 8 squares - At most 1 point per square because the diameter of the square is $\delta / \sqrt{2} < \delta$. - At most 7 other points can be in $R$. (this constant 7 can actually be improved with more refined geometric packing argument) The full algorithm here: Closest-Pair($p_1, p_2, \dots, p_n$): - Compute vertical line $L$ such that half the points are on each side of the line - $\delta_1 \leftarrow$ Closest-Pair(points in the left half) - $\delta_1 \leftarrow$ Closest-Pair(points in the right half) - $\delta \leftarrow min{\delta_1, \delta_2}$ - Delete all points further than $\delta$ from line $L$. - sort remaining points by y-coordinate - Scan points in y-order and compare distance between each point and next 7 neighbors. If any of these dsitances is less than $\delta$, update $\delta$. - return $\delta$. # Median and Selection Selection: given $n$ elements from a totally ordered universe, find $k$th smallest. - Minimum $k=1$; maximum $k=n$. - Median: $k = \lfloor (n+1) /2 \rfloor$. - $O(n)$ compares for min or max - $O(n \log n )$ compares by sorting. Applications: order statstics; find the "top $k$"; bottleneck paths, ... Q: can we do it with $O(n)$ compares? A: Yes! Selection is easier than sorting. Randomized quickselect solution - pick a random pivot element $p \in A$ - 3-way partition the array into $L$, $M$, and $R$. - Recur in *one* subarray- the one containing the $k$th element. Quick-Select($A,K$) - pick pivot $p \in A$ uniformly at random - $(L,M,R) \leftarrow$ Paritition-3-way$(A, p)$ - If $(k \leq |L|)$, return Quick-Select($L,k$) - Else if $(k > |L| + |M|)$, return Quick-Select($R, k-|L| - |M|$) - Else if $(k = |L|)$ return $p$. # Master Theorem Recurrences **Master theorem.** Let $a \geq 1, b\geq 2,$ and $c \geq 0$ and suppose that $T(n)$ is a function on the non-negative integers that satisfies the recurrence. $$T(n) = aT(\frac{n}{b}) + \Theta(n^c)$$ with $T(0)=0$ and $T(1) = \Theta(1)$, where $n/b$ means either $\lfloor n/b \rfloor$ or $\lceil n/b \rceil$. Then, - Case 1: If $c > \log_b a$, then $T(n) = \Theta (n^c)$ - Case 1: If $c = \log_b a$, then $T(n) = \Theta (n^c \log n)$ - Case 1: If $c < \log_b a$, then $T(n) = \Theta (n^{\log_b a})$ $a$ is the number of subproblems each of size $\frac{n}{b}$ and $\Theta (n^c)$ is the work to divide and combine subproblems. Examples: - For binary search the recurrence relation ship is $T(n) = T(n/2) + O(1)$ because $a,b,c = 1, 2, 0$ - For merge sort: $T(n) = 2T(n/2)+O(n)$ where $a, b, c = 2,2,1$ Some gaps in master theorem. These situations do not apply: - the number of subproblems (a) is not a constant - the number of subproblems is less than 1. - The work to divide and combine subprobelms is not $\Theta(n^c # Integer Multiplication Integer **addition**: given two $n$-bit integers $a$ and $b$, compute $a+b$. Integer **subtraction**: given two $n$-bit integers $a$ and $b$, compute $a-b$. **grade-school algorithm**: $\Theta(n)$ bit operations. - grade-school addition and subtraction algorithms are optimal. Integer **multiplication**: given two $n$-bit integers $a$ and $b$, compute $a \times b$. **grade-school algorithm (long multiplication)**: $\Theta(n^2)$ bit operations. - Conjecture: [Kolmogorov 1956] said that grade-school algorithm was optimal - Theorem [Karatsuba 1960] proved that the conjecture is false. The **divide-and-conquer multiplication** To multiply two $n$-bit integers $x$ and $y$: - divide $x$ and $y$ into low- and high-order bits - multiply four $\frac{1}{2}n$-bit integers, recursively. - add and shfit to obtain result $m = \lceil n/2 \rceil$ $a = \lfloor x/2^m \rfloor$ $b = x mod 2^m$ $c = \lfloor y/2^m \rfloor$ $d = y mod 2^m$ - use bit shifting to compute 4 terms. $xy = (2^m a + b)(2^m c + d) = 2^{2m} ac + 2^m (bc+ ad) + bd$ - Now, when you multiply say $bc$, it would be multiplying two numbers of length $n/2$ Ex: $x=100001101$ $y=11100001$ where $a = 1000$, $b=1101$, $c=1110$, $d=0001$. So, $x = a \times 2^4 + b$ **Multiply($x,y,n$):** - If ($n=1$) - return $x \times y$ - Else - $m \gets \lceil n/2 \rceil$ - $a \gets \lfloor x/2^m \rfloor$; $b \gets x mod 2^m$ - $c \gets \lfloor y/2^m \rfloor$; $d \gets y mod 2^m$ - $e \gets$ Multiply($a,c,m$) - $f \gets$ Multiply($b,d,m$) - $g \gets$ Multiply($b,c,m$) - $h \gets$ Multiply($a,d,m$) - Return $2^{2m} e + 2^m (g+h) + f$ The recurrence solution: $T(n) = 4T(n/2) + \Theta(n)$ - $a=4, b=2, c=1$, so $log_b a = 2 > 1 = c$ the answer is $\Theta(n^2)$. - This does not save any more time How can we optimize? This is the **Karatsuba trick**. To compute that middle term $bc+ad$ (which takes two multiplications), we can use addition with the terms we already know. $(a+b) \cdot (c+d) = ac + ad + bc +bd$ $(a+b) \cdot (c+d) - ac - bd = ad + bc$ - using this identity, we only need to multiple three $n/2$-bit integers, recursively. **Karatsuba-Multiply($x,y,n$):** - If ($n=1$) - return $x \times y$ - Else - $m \gets \lceil n/2 \rceil$ - $a \gets \lfloor x/2^m \rfloor$; $b \gets x mod 2^m$ - $c \gets \lfloor y/2^m \rfloor$; $d \gets y mod 2^m$ - $e \gets$ Karatsuba-Multiply($a,c,m$) - $f \gets$ Karatsuba-Multiply($b,d,m$) - $g \gets$ Karatsuba-Multiply($|a-b|, |c-d|,m$) - Flip the sign of $g$ if needed - Return $2^{2m} e + 2^m (e+f-g) + f$ ## Analysis Proposition: Karatsuba's algorithm reuqires $O(n^{1.575})$ bit operations to multiply two $n$-bit integers. Proof: apply case 3 of the master theorem to the recurrence $$T(n) = \left\{ \begin{array}{lr} \Theta(1), & \text{if } n = 1\\ 3T(\lceil n/2 \rceil) + \Theta(n), & \text{if } n > 1 \end{array} \right.

$\Rightarrow T(n) = \Theta(n^{\log_2 3}) = O(n^{1.585})$

This algorithm will be faster than the grade school algorithm for about 320-640 bits.

Matrix Multiplication

Dot Product is when you are given two length-$n$ vectors $a$ and $b$, and you compute $c = a \cdot b$. Grade-school solution: $\Theta(n)$ arithmetic operations.

• this is asymptotically optimal.

Matrix multiplication is when you are given two $n$-by-$n$ matrices $A$ and $B$, and you compute $C=AB$. Grade-school solution: $\Theta(n^3)$ arithmetic operations.

Divvide and conquer method:

• divide: partition $A$ and $B$ into $n/2$-by-$n/2$ blocks.
• conquier: multiply $8$ pairs of $n/2$-by-$n/2$ matrices, recursively
• combine: add appropriate products using 4 matrix additions. $C = A \times B$

$$\begin{bmatrix} C_{1,1} & C_{1,2}\\ C_{2,1} & C_{2,2}\\ \end{bmatrix} = \begin{bmatrix} A_{1,1} & A_{1,2}\\ A_{2,1} & A_{2,2}\\ \end{bmatrix} \times \begin{bmatrix} B_{1,1} & B_{1,2}\\ B_{2,1} & B_{2,2}\\ \end{bmatrix}$$

$C_{1,1} = (A_{1,1} \times B_{1,1}) + (A_{1,2} \times B_{2,1})$ $C_{1,2} = (A_{1,1} \times B_{1,2}) + (A_{1,2} \times B_{2,2})$ $C_{2,1} = (A_{2,1} \times B_{1,1}) + (A_{2,2} \times B_{2,1})$ $C_{2,2} = (A_{2,1} \times B_{1,2}) + (A_{2,2} \times B_{2,2})$

Applying master thorem (case 3): $T(n) = 8T(n/2) + \Theta(n^2) \Rightarrow T(n) = \Theta(n^3)$

We can optimize with the key idea that we can multiply two $n$-by-$n$ matrices via $7$ $n/2$-by-$n/2$ matrix multiplications (plus $11$ additions and $7$ subtractions)

$P_1 \gets A_{1,1} \times (B_{1,2} - B_{2,2})$ $P_2 \gets (A_{1,1} - A_{1,2}) \times B_{2,2}$ $P_3 \gets (A_{2,1} - A_{2,2}) \times B_{1,1}$ $P_4 \gets (A_{2,2} \times (B_{2,1}) - B_{1,1})$ $P_5 \gets (A_{1,1} + B_{2,2}) \times (A_{1,1} + B_{2,2})$ $P_6 \gets (A_{1,2} \times B_{2,2}) + (B_{2,1} \times B_{2,2})$ $P_7 \gets (A_{1,1} \times B_{2,1}) + (B_{1,1} \times B_{1,2})$

Proof: $C_{1,2} = P_1 + P_2 = A_{1,1} \times (B_{1,2} - B_{2,2}) + (A_{1,1} - A_{1,2}) \times B_{2,2} = (A_{1,1} \times B_{1,2}) + (A_{1,2} \times B_{2,2})$

(assuming $n$ is a power of $2$) Strassen($n,A,B$):

• If ($n=1$)
  • return $A \times B$
• Partition $A$ and $B$ into $n/2$-by-$n/2$ blocks.
• $P_1 \gets$ Strassen($n/2, A_{1,1}, (B_{1,2} - B_{2,2})$)
• $P \gets ...$ (the rest of the P from above)
• $C_{1,1} = P_5 + P_4 - P_2 + P_6$
• $C_{1,2} = P_1 + P_2$
• $C_{2,1} = P_3 + P_4$
• $C_{2,2} = P_1 + P_5 - P_3 - P_7$
• Return $C$

Analysis

Theorem: Strassen's algorithm requires $O(n^{2.81})$ arithmetic operations to multiply two $n$-by-$n$ matrcies.

Proof: when $n$ is a power of $2$, you can apply master theorem: $T(n) = 7T(n/2) + \Theta(n^2) \Rightarrow T(n) = \Theta(n^{\log_2 7}) = O(n^{2.81})$

• When $n$ is not a power of 2, you pad the matrices with zeros to be $n'$ by $n'$, where $n \leq n < 2n$ and $n'$ is a power of two.