Divide and Conquer

Notes

Skiena Chapter 4

Powerful technique for solving problems - break problems down into smaller problems.

The basic idea behind divide and conquer is, you are looking for a problem where it is faster to solve the problem in pieces AND TO MERGE THE PIECES than it is to solve the overall problem.

Merge sort is a good example of divide and conquer: merge must take less time than solving the two subproblems, which will make the algorithm efficient overall. Merge sort is just merging two lists, which is O(n), and getting each of the lists costs O(n log n).

Analyzing divide-and conquer algorithms depends on solving the asymptotic behavior of the divide-and-conquer algorithm's recurrence relations.

Recurrence Relations

A recurrence relation is an alternative representation for functions. (Somewhat related is Stephen Wolfram's idea that the universe is fundamentally digital, and that we need cellular autonoma and self-replicating patterns, to effectively understand and describe the world.)

We can represent a polynomial using a recurrence. Multiplication is achieved by having a recurrence relation in which things are added together:

$ a_n = a_{n-1} + 1, a_1 = 1 \rightarrow a_n = n $

We can also represent exponential functions by multiplying successive terms together:

$ a_n = 2 a_{n-1}, a_1 = 1 \rightarrow a_n = 2^{n-1} $

We can also describe more unusual, or harder-to-describe, functions, like the factorial function, with very succinct notation:

$ a_{n} = n a_{n-1}, a_1 = 1 \rightarrow a_n = n! $

Resources

MIT OCW

6.046 design and analysis of algorithms

Divide and conquer for FFT: https://www.youtube.com/watch?v=iTMn0Kt18tg

Divide and conquer for Van Emde Boas trees: https://www.youtube.com/watch?v=hmReJCupbNU

Advanced dynamic programming and divide-and-conquer: https://www.youtube.com/watch?v=Tw1k46ywN6E