Divide-and-conquer algorithms


The divide-and-conquer strategy solves a problem by:
1. Breaking it into subproblems that are themselves smaller instances of the same type of
problem
2. Recursively solving these subproblems
3. Appropriately combining their answers
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 multi-
plying numbers, one that is much more efficient than the method we all learned in elementary
school!

Download files here

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s