Go to the first, previous, next, last section, table of contents.

Divide And Conquer

One central task of a C compiler is to assign variables and temporaries to registers.

Possibly the prettiest way to solve this problem is to re-express it as a graph-coloring problem, in which every node in the graph is to be assigned a color, no two nodes connected by an edge may have the same color, and we wish to use the minimum number of colors to color the entire graph. (1).

This problem is known to be NP-Complete in general, which means that for realistic-sized problems we cannot usually expect to find the best possible solution, only a good solution.

One quite pretty way of finding a good solution is to iteratively remove all the easy-to-color parts of the graph, color any 'hard' core remaining (often there will be none) and then color the remaining parts one-by-one as we add them back. This will often color with ease graphs that at first blush look intimidatingly difficult.

One may take this heuristic as a metaphor for divide-and-conquer problem-solving in general: We are frequently faced with a problem which is too complex to solve all at once. A ubiquituous technique for such problems is to divide them into subproblems, solve the subproblems individually, and then merge the subsolutions into a solution to the entire problem. (Many, many algorithms from sorting to integer factoring may be understood as simply divide-and-conquer applied with particular ways of doing the subdivision and merging steps.)

As usual with the techniques discussed in this chapter, there is no simple recipe for dividing an arbitrary problem or merging the subsolutions: Creativity and insight are required and rewarded.

But we may draw a very general lesson from the graph-coloring heuristic:

Solve the most important subproblem first.

Depending on the particular problem, the "most important" subproblem may be the most highly constrained one, the most novel one, the most difficult one, or the one most critical to quality of the resulting solution.

In any event, each subproblem solved usually reduces the degrees of freedom left for solving the succeeding subproblems, so it pays to select the order of solution carefully, making the most of the extra degrees of freedom available in the first subproblem.

Thus, for example, if the most critical design goal in a given application is minimizing disk I/O, start by designing the data structures and algorithms involved in disk I/O, then design the other parts of the application to work well with them without degrading their performance. (Muq was designed in somewhat this fashion.)

Go to the first, previous, next, last section, table of contents.