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 k² problems of “size” N/k². Continuing in this fashion, one reduces to kⁿ problems of size N/kⁿ. If N/kⁿ is small, a problem of that size should be easy to solve. For example, if N = 2ⁿ 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 N² 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.