2008 Serge Lang Undergraduate Lecture
The 2008 Serge Lang Undergraduate Lecture will be delivered by Peter W. Jones on November 5, 2008.
MUSA and the Department of Mathematics, University of California, Berkeley, present
The 2008 Serge Lang Undergraduate Lecture
Peter W. Jones
Department of Mathematics
Yale University
"Divide and Conquer"
November 5, 2008
10 Evans Hall - 4:10-5:00pm
Abstract: Divide and Conquer is a method used to solve a wide
variety of problems. The idea is deceptively simple. One starts with a
"large" and difficult problem of “size” N. To solve it, one chops the
problem into k subproblems of size N/k, where k is some fixed number
(e.g. k = 2). Now these k smaller problems may still be difficult, but
because they are smaller they may be slightly easier to solve. One then
divides each of the k smaller problems into k even smaller problems. One
thus obtains k2 problems of “size” N/k2. Continuing in this fashion, one reduces to kn problems of size N/kn. If N/kn is small, a problem of that size should be easy to solve. For example, if N = 2n
and k = 2, we get N problems of size 1. The original problem is then
solved by piecing back together the solutions to the small problems of
size 1.
This idea is perhaps more of a philosophy than a well determined method,
because each given problem will probably need a special way to cut into
k subproblems. It turns out that this idea is remarkably effective and
has deep consequences (even when dealing with infinite sets). We will
present several examples and discuss a (shocking!) open problem. Some of
the examples include:
1. Geometry of sets (how to cut sets into small simple pieces). We will
outline the so called Whitney decomposition of open sets of Euclidean
space into nice squares (in two dimensions) or cubes (in higher
dimensions). This simple method has beautiful consequences for studying
functions defined on sets.
2. Constructions of “fractal curves”. Here we take a bit of liberty with
the usual definition of Divide and Conquer to show how powerful the
general philosophy is. We use the philosophy to reduce the construction
of an entire curve to the construction of one simple polygonal arc,
consisting for example of four intervals.
3. How to multiply two numbers! Let a and b be two N digit integers.
(Base two instead of base ten is more fun.) How long does it take to
multiply them together? Now if we add a + b, it takes CN operations for
some small constant C. (This is what one learns in first grade.) The
usual method of multiplication takes N2 operations. But
perhaps it can be done in CN operations, so that multiplication is “as
easy” as addition! Amazingly, this problem remains open. Divide and
conquer algorithms provide methods that are only slightly worse that CN
operations. (One needs to multiply CN by some factors that are
logarithmic in N.) There are deep relations to the “Fast Fourier
Transform”.
There only prerequisites for this talk are knowledge of calculus and elementary plane geometry.