In [3]:
from IPython.display import display
from IPython.display import HTML
import IPython.core.display as di # Example: di.display_html('<h3>%s:</h3>' % str, raw=True)
# This line will hide code by default when the notebook is exported as HTML
di.display_html('<script>jQuery(function() {if (jQuery("body.notebook_app").length == 0) { jQuery(".input_area").toggle(); jQuery(".prompt").toggle();}});</script>', raw=True)
# This line will add a button to toggle visibility of code blocks, for use with the HTML export version
di.display_html('''<button onclick="jQuery('.input_area').toggle(); jQuery('.prompt').toggle();">Toggle code</button>''', raw=True)
The real work is done piecemeal, in three different places: in the partitioning of problems into subproblems; at the very tail end of the recursion, when the subproblems are so small that they are solved outright; and in the gluing together of partial answers. These are held together and coordinated by the algorithm’s core recursive structure. As an introductory example, we’ll see how this technique yields a new algorithm for multiplying numbers, one that is much more efficient than the method we all learned in elementary school!
| $\rm{lgN}$ | $$\sqrt{N} $$ | $$ {N}$$ | $${N \rm{lg} N}$$ | $${N \log N^2}$$ | $ {N^{\frac32}} $ | $${N^2}$$ |
|---|---|---|---|---|---|---|
| 3 | 3 | 10 | 33 | 110 | 32 | 100 |
| 7 | 10 | 100 | 664 | 4410 | 1000 | 10000 |
| 10 | 32 | 1000 | 9966 | 993317 | 31623 | 1000000 |
| 13 | 100 | 10000 | 132877 | 1765633 | 1000000 | 100000000 |
| 17 | 316 | 100000 | 1660964 | 27588016 | 31622777 | 10000000000 |
In [4]:
%pylab inline
In [5]:
# Import libraries
from __future__ import absolute_import, division, print_function
import math
from time import time
import matplotlib.pyplot as pyplt
Incidentally, this function $\log N$ appears repeatedly in CS, in many guises. Here’s a sampling:
Divide-and-conquer algorithms often follow a generic pattern: they tackle a problem of size n by recursively solving, say, $a$ subproblems of size $n/b$ and then combining these answers in $O(n^d)$ time, for some a, b, d > 0 (in the multiplication algorithm, a = 3, b = 2, and d = 1). Their running time can therefore be captured by the equation $T(n) = aT(\lceil n/b \rceil) + O(n^d)$. We next derive a closed-form solution to this general recurrence so that we no longer have to solve it explicitly in each new instance.
If $T(n) = aT(\lceil n/b \rceil) + O(n^d)$ for some constants a > 0, b > 1, and d ≥ 0, then
$T(n) = \begin{cases} O(n^d), & \mbox{if } d \mbox{ is} > \log_{b}a \\ O(n^d \, \log \, n), & \mbox{if } d \mbox{ is} = \log_{b}a \\ O(n^d \, \log_{b} \, a), & \mbox{if} d \mbox{ is} < \log_{b}a \end{cases}$
This single theorem tells us the running times of most of the divide-and-conquer procedures we are likely to use.
Below is an implementation of MergeSort, which is another divide and conquer algorithm that has the recurrence relation
In [25]:
# My implementation of Mergesort
# Input: an list of integers
# Output: A sorted list of integers
def merge(x,y):
''' Returns a merge sorted list of integers
>>> merge([10,2], [5,3])
[2,3,5,10]
'''
lenght_x = len(x)
lenght_y = len(y)
if lenght_x == 0:
return y
if lenght_y == 0:
return x
if(x[0] <= y[0]):
return [x[0]] + merge(x[1:lenght_x],y)
else:
return [y[0]] + merge(x, y[1:lenght_y])
def mergeSort(a):
"""Returns a sorted list of integers
>>> mergeSort([10, 2, 5, 3, 7, 13, 1, 6])
[1, 2, 3, 3, 5, 6, 7, 10, 13]
"""
n = len(a)
if n > 1:
return merge(mergeSort(a[0: int(math.floor(n/2))]),mergeSort(a[int(math.floor(n/2)):n]))
else:
return a
In [26]:
mergeSort([10, 2, 5, 3, 7, 13, 1, 6])
Out[26]:
function multiply(x, y)
Input: Positive integers x and y, in binary
Output: Their product
n = max(size of x, size of y)
if n = 1:
return xy
xL, xR = leftmost celing(n/2), rightmost floor(n/2) bits of x
yL, yR = leftmost celing(n/2), rightmost floor(n/2) bits of y
P1 = multiply(xL,yL)
P2 = multiply(xR,yR)
P3 = multiply(xL + xR,yL + yR)
return P1 × 2^n + (P3 −P1 −P2) × 2^(n/2) + P2
Suppose $x$ and $y$ are two $n$-bit integers, and assume for convenience that $n$ is a power of 2 (the more general case is hardly any different). As a first step toward multiplying $x$ and $y$, split each of them into their left and right halves, which are $n/2$ bits long. For instance, if $x = 10110110_2$ (the subscript 2 means “binary”) then $xL = 1011_2$, $xR = 0110_2$, and $x = 1011_2 × 2^4 + 0110_2$.
The product of $x$ and $y$ can then be rewritten as $$xy = (2^{n/2}xL + xR)(2^{n/2}yL + yR) = 2^n xL yL + 2^{n/2} (xL yR + xR yL) + xRyR$$ We will compute xy via the expression on the right.
The significant operations are the four $n/2$-bit multiplications, $xLyL, \, xLyR, \, xRyL, \,xRyR$; these we can handle by four recursive calls. Thus our method for multiplying n-bit numbers starts by making recursive calls to multiply these four pairs of $n/2$-bit numbers (four subproblems of half the size), and then evaluates the preceding expression in $O(n)$ time. Writing $T(n)$ for the overall running time on n-bit inputs, we get the recurrence relation $$T(n) = 4T(n/2)+O(n)$$ We will soon see general strategies for solving such equations. In the meantime, this particular one works out to $O(n^2)$, the same running time as the traditional grade-school multiplication technique. So we have a radically new algorithm, but we haven’t yet made any progress in efficiency.
How can our method be sped up?
This is where Gauss’s trick comes to mind. Although the expression for $xy$ seems to demand four $n/2$-bit multiplications, as before just three will do:
The resulting algorithm has an improved running time of $T(n) \leq3T(n/2)+O(n)$. The point is that now the constant factor improvement, from 4 to 3, occurs at every level of the recursion, and this compounding effect leads to a dramatically lower time bound of $O(n^{1.59})$.
In [ ]: