Today's agenda:
We've seen a few divide-and-conquer algorithms already, so let's look at the high-level approach. For a problem $A$ and instance $\mathcal{I}_A$:
Base Case: If $\mathcal{I}_A$ is small, solve directly.
Inductive Step:
As we'll see, each algorithmic paradigm has high-level strategies to
Induction -- why and how?
Induction provides a natural framework for divide-and-conquer algorithms.
The base case of the induction requires us to prove that the algorithm works for the base case.
For the induction step, we use the inductive hypothesis that the solutions to the smaller instances are correct. Then, we must prove that the combine step correctly produces the desired solution.
We've seen that recurrences can capture the behavior of divide-and-conquer algorithms - they simply capture the cost of recursively solving smaller instances and then combining the solutions.
The general form of the work is:
$$ W(n) = W_{\mathsf{\small divide}}(n) + \sum_{i=1}^{k}W(n_i) + W_{\mathsf{\small combine}}(n) + 1 $$The general form for the span is:
$$ S(n) = S_{\mathsf{\small divide}}(n) + \max_{i=1}^{k}S(n_i) + S_{\mathsf{\small combine}}(n) + 1 $$Let's look at how Merge Sort fits into this framework.
$$ \begin{array}{l} \mathit{mergeSort}~a = \\ ~~~~\texttt{if}~|a| \leq 1~\texttt{then} \\ ~~~~~~~~a \\ ~~~~\texttt{else} \\ ~~~~~~~~\texttt{let} \\ ~~~~~~~~~~~~(l,r) = \mathit{splitMid}~a \\ ~~~~~~~~~~~~(l',r') = (\mathit{mergeSort}~l \mid\mid{} \mathit{mergeSort}~r) \\ ~~~~~~~~\texttt{in} \\ ~~~~~~~~~~~~\mathit{merge} (l',r') \\ ~~~~~~~~\texttt{end} \end{array}\ $$For the correctness, we need to show that Merge Sort truly sorts the list. Let's perform induction:
Base case: We correctly sort a singleton list.
Induction Step: We assume that we can correctly sort the two halves of the list (by the inductive hypothesis). The final step would be to prove that the merge step works correctly to combine two sorted lists into one sorted list.
For the running time, recall that we characterized the work/span of Merge Sort as:
$$ W(n) = 2W(n/2) + O(n) $$and
$$ S(n) = S(n/2) + O(\log n) $$This fits into the framework above: the divide step takes $O(1)$ time, there are 2 concurrent recursive calls, and merging takes $O(n)$ work and $O(\log n)$ span.
We developed a contraction-based algorithm for this problem, but let's look at a divide-and-conquer strategy.
Remember that we looked at taking prefix sums for intuition. Let's reuse that example:
$\texttt{prefix_sum}([2,1,3,2,2,5,4,1]) \rightarrow ([0, 2, 3, 6, 8, 10, 15, 19], 20)$
Divide and Conquer Approach
Instead of contracting pairs of entries what if we just split the list and recursively compute prefix sums?
$\texttt{prefix_sum}([2,1,3,2]) \rightarrow (l, l') = (\langle 0, 2, 3, 6\rangle, 8)$
$\texttt{prefix_sum}([2,5,4,1]) \rightarrow (r, r') = (\langle 0, 2, 7, 11\rangle, 12)$
Now, it's easy to see that $l$ already gives us half the solution - how do we get the result by combining solutions?
All we have to do is to add the sum of the first half to all of the elements of $r$ and to $r'$.
$a = [2,1,3,2,2,5,4,1]$
We need to get:
$\texttt{prefix_sum}([2,1,3,2,2,5,4,1]) \rightarrow ([0, 2, 3, 6, 8, 10, 15, 19], 20)$
Recursively run $\texttt{prefix_sum}$ on both halves of the list:
$\texttt{prefix_sum}([2,1,3,2]) \rightarrow (l, l') = (\langle 0, 2, 3, 6\rangle, 8)$
$\texttt{prefix_sum}([2,5,4,1]) \rightarrow (r, r') = (\langle 0, 2, 7, 11\rangle, 12)$
Generate $y$, the right half of the output by adding $l'$ to every element in $r$:
$y = [0+8,\ 2+8,\ 7+8,\ 11+8] = [8, 10, 15, 19]$
Append $y$ to $l$ and calculate the final sum by adding $l'$ to $r'$.
$([0, 2, 3, 6, 8, 10, 15, 19], 20)$
How do we prove the correctness of this algorithm?
Base Case: For empty and singleton lists, we compute the correct result.
Induction Step: For the induction hypothesis, we assume that we correctly compute the scan results for the two halves of the list. For the combine step, we compute $f(l', x)$ for all $x\in r$. Why is this the correct result for the right half of the list?
Example
$\texttt{prefix_sum}([2,1,3,2,2,5,4,1]) \rightarrow$
$\texttt{prefix_sum}([2,1,3,2]) \rightarrow (l, l') = (\langle 0, 2, 3, 6\rangle, 8)$
$\texttt{prefix_sum}([2,5,4,1]) \rightarrow (r, r') = (\langle 0, 2, 7, 11\rangle, 12)$
$y = [0+8,\ 2+8,\ 7+8,\ 11+8] = [8, 10, 15, 19]$
$l +\!\!+ y = ([0, 2, 3, 6, 8, 10, 15, 19], 20)$
Proof
We know that $l' = f(l[(n/2)-1], a[(n/2)-1])$. Since $l[(n/2)-1]$ is a correct scan result and $a[(n/2)-1])$ is the next element to be added, then $l'$ is the correct scan result for the left side of the list.
Consider the first element of $y$, it is $f(l', id) = l' = f(l[(n/2)-1], a[(n/2)-1])$.
This is the correct scan result for $a$ at position $n/2 + 1$.
We can similarly show that each successive element in $y$ is the correct scan result for $a$ in the right half of the solution.
Finally, since $f$ is associative we can see that $f(l', r')$ is the correct "sum" result as well. Therefore, $\texttt{prefix_sum}$ is correct. $\blacksquare$
Runtime Analysis
Assuming that $f(n)$ can be computed in constant time, we get the following recurrences for work and span:
$$ W(n) = 2W(n/2) + O(n)$$and
$$ S(n) = S(n/2) + O(1) $$Thus the work is $O(n \log n)$ and the span is $O(\log n)$.
Is this algorithm work-efficient? Why or why not?
Do you find scanDC more or less intuitive than the version using contract?
def scanDC(f, id_, a):
# space = len(a) * ' ' # for printing
# print(space, 'a=', a)
if len(a) == 0:
return ([], id_)
elif len(a) == 1:
return ([id_], a[0])
else:
b = a[:len(a)//2]
c = a[len(a)//2:]
left, L = scanDC(f, id_, b)
right, R = scanDC(f, id_, c)
updated_right = [f(L, x) for x in right]
return left + updated_right, f(L, R)
def add(x,y):
return x + y
scanDC(add, 0, [2,1,3,2,2,5,4,1])
([0, 2, 3, 6, 8, 10, 15, 19], 20)
def ternaryScanDC(f, id_, a):
# space = len(a) * ' ' # for printing
# print(space, 'a=', a)
if len(a) == 0:
return ([], id_)
elif len(a) == 1:
return ([id_], a[0])
else:
mid1 = len(a) // 3
mid2 = 2*len(a) // 3
l = a[:mid1]
m = a[mid1:mid2]
r = a[mid2:]
left, L = ternaryScanDC(f, id_, l)
mid, M = ternaryScanDC(f, id_, m)
right, R = ternaryScanDC(f, id_, r)
# assume the following is equivalent to map
# with work of O(n) and span of O(1)
updated_mid = [f(L, x) for x in mid]
M = f(L,M)
updated_right = [f(M, x) for x in right]
return left + updated_mid + updated_right, f(M, R)
def gt(x,y):
return max(x,y)
ternaryScanDC(gt, 0, [2,1,3,2,2,5,4,1])
([0, 2, 2, 3, 3, 3, 5, 5], 5)
Is $\texttt{ternaryScanDC}$ any more efficient?
$W(n) = 3W(n/3) + O(n)$
This is balanced.
$W(n) \in O(n \log_3 n)$
What about the span?
$S(n) = S(n/3) + 1$
Balanced.
There are $\log_3(n)$ levels.
$S(n) \in O(\log_3 n)$