Next: Dynamic Programming Up: Techniques Previous: Implementation Challenges

# Breaking Problems Down

One of the most powerful techniques for solving problems is to break them down into smaller, more easily solved pieces. Smaller problems are less overwhelming, and they permit us to focus on details that are lost when we are studying the entire problem. For example, whenever we can break the problem into smaller instances of the same type of problem, a recursive algorithm starts to become apparent.

Two important algorithm design paradigms are based on breaking problems down into smaller problems. Dynamic programming typically removes one element from the problem, solves the smaller problem, and then uses the solution to this smaller problem to add back the element in the proper way. Divide and conquer typically splits the problem in half, solves each half, then stitches the halves back together to form a full solution.

Both of these techniques are important to know about. Dynamic programming in particular is a misunderstood and underappreciated technique. To demonstrate its utility in practice, we present no fewer than three war stories where dynamic programming played the decisive role.

The take-home lessons for this chapter include:

• Many objects have an inherent left-to-right ordering among their elements, such as characters in a string, elements of a permutation, points around a polygon, or leaves in a search tree. For any optimization problem on such left-to-right objects, dynamic programming will likely lead to an efficient algorithm to find the best solution.
• Without an inherent left-to-right ordering on the objects, dynamic programming is usually doomed to require exponential space and time.
• Once you understand dynamic programming, it can be easier to work out such algorithms from scratch than to try to look them up.
• The global optimum (found, for example, using dynamic programming) is often noticeably better than the solution found by typical heuristics. How important this improvement is depends upon your application, but it can never hurt.
• Binary search and its variants are the quintessential divide-and-conquer algorithms.

Next: Dynamic Programming Up: Techniques Previous: Implementation Challenges

Algorithms
Mon Jun 2 23:33:50 EDT 1997