Next: Resources Up: Techniques Previous: Implementation Challenges

# How to Design Algorithms

Designing the right algorithm for a given application is a difficult job. It requires a major creative act, taking a problem and pulling a solution out of the ether. This is much more difficult than taking someone else's idea and modifying it or tweaking it to make it a little better. The space of choices you can make in algorithm design is enormous, enough to leave you plenty of freedom to hang yourself.

This book is designed to make you a better algorithm designer. The techniques presented in Part I of this book provide the basic ideas underlying all combinatorial algorithms. The problem catalog of Part II will help you with modeling your application and point you in the right direction of an algorithm or implementation. However, being a successful algorithm designer requires more than book knowledge; it requires a certain attitude, the right problem-solving approach. It is difficult to teach this mindset in a book; yet getting it is essential to become a successful designer.

The key to algorithm design (or any other problem-solving task) is to proceed by asking yourself a sequence of questions to guide your thought process. What if we do this? What if we do that? Should you get stuck on the problem, the best thing to do is move onto the next question. In any group brainstorming session, the most useful person in the room is the one who keeps asking, ``Why can't we do it this way?'' not the person who later tells them why. Because eventually she will stumble on an approach that can't be shot down.

Towards this end, we provide below a sequence of questions to guide your search for the right algorithm for your problem. To use it effectively, you must not only ask the questions, but answer them. The key is working through the answers carefully, by writing them down in a log. The correct answer to, ``Can I do it this way?'' is never ``no,'' but ``no, because ....'' By clearly articulating your reasoning as to why something doesn't work, you can check if it really holds up or whether you have just glossed over a possibility that you didn't want to think hard enough about. You will be surprised how often the reason you can't find a convincing explanation for something is because your conclusion is wrong.

An important distinction to keep aware of during any design process is the difference between strategy and tactics. Strategy represents the quest for the big picture, the framework around which we construct our path to the goal. Tactics are used to win the minor battles we must fight along the way. In problem solving, it is important to check repeatedly whether you are thinking on the right level. If you do not have a global strategy of how you are going to attack your problem, it is pointless to worry about the tactics. An example of a strategic question is, ``How best can I model my application as a graph algorithm problem?'' A tactical question might be, ``Should I use an adjacency list or adjacency matrix data structure to represent my graph?'' Of course, such tactical decisions are critical to the ultimate quality of the solution, but they can be properly evaluated only in light of a successful strategy.

When faced with a design problem, too many people freeze up in their thinking. After reading or hearing the problem, they sit down and realize that they don't know what to do next. They stare into space, then panic, and finally end up settling for the first thing that comes to mind. Avoid this fate. Follow the sequence of questions provided below and in most of the catalog problem sections. We'll tell you what to do next!

Obviously, the more experience you have with algorithm design techniques such as dynamic programming, graph algorithms, intractability, and data structures, the more successful you will be at working through the list of questions. Part I of this book has been designed to strengthen this technical background. However, it pays to work through these questions regardless of how strong your technical skills are. The earliest and most important questions on the list focus on obtaining a detailed understanding of the problem and do not require specific expertise.

This list of questions was inspired by a passage in that wonderful book about the space program The Right Stuff [Wol79]. It concerned the radio transmissions from test pilots just before their planes crashed. One might have expected that they would panic, so that ground control would hear the pilot yelling Ahhhhhhhhhhh --, terminated only by the sound of smacking into a mountain. Instead, the pilots ran through a list of what their possible actions could be. I've tried the flaps. I've checked the engine. Still got two wings. I've reset the --. They had ``the Right Stuff.'' Because of this, they sometimes managed to miss the mountain.

I hope this book and list will provide you with ``the Right Stuff'' to be an algorithm designer. And I hope it prevents you from smacking into any mountains along the way.

1. Do I really understand the problem?

1. What exactly does the input consist of?
2. What exactly are the desired results or output?
3. Can I construct an example input small enough to solve by hand? What happens when I try to solve it?
4. How important is it to my application that I always find an exact, optimal answer? Can I settle for something that is usually pretty good?
5. How large will a typical instance of my problem be? Will I be working on 10 items? 1,000 items? 1,000,000 items?
6. How important is speed in my application? Must the problem be solved within one second? One minute? One hour? One day?
7. How much time and effort can I invest in implementing my algorithm? Will I be limited to simple algorithms that can be coded up in a day, or do I have the freedom to experiment with a couple of approaches and see which is best?
8. Am I trying to solve a numerical problem? A graph algorithm problem? A geometric problem? A string problem? A set problem? Might my problem be formulated in more than one way? Which formulation seems easiest?

2. Can I find a simple algorithm or heuristic for the problem?

1. Can I find an algorithm to solve my problem correctly by searching through all subsets or arrangements and picking the best one?

1. If so, why am I sure that this algorithm always gives the correct answer?
2. How do I measure the quality of a solution once I construct it?
3. Does this simple, slow solution run in polynomial or exponential time? Is my problem small enough that this brute-force solution will suffice?
4. If I can't find a slow, guaranteed correct algorithm, why am I certain that my problem is sufficiently well-defined to have a correct solution?
2. Can I solve my problem by repeatedly trying some simple rule, like picking the biggest item first? The smallest item first? A random item first?

1. If so, on what types of inputs does this heuristic work well? Do these correspond to the data that might arise in my application?
2. On what types of inputs does this heuristic work badly? If no such examples can be found, can I show that it always works well?
3. How fast does my heuristic come up with an answer? Does it have a simple implementation?

3. Is my problem in the catalog of algorithmic problems in the back of this book?

1. If it is, what is known about the problem? Is there an implementation available that I can use?
2. If I don't see my problem, did I look in the right place? Did I browse through all the pictures? Did I look in the index under all possible keywords?
3. Are there relevant resources available on the World-Wide Web? Did I do a Lycos, Alta Vista, or Yahoo search? Did I go to the WWW page associated with this book, ?

4. Are there special cases of the problem that I know how to solve exactly?

1. Can I solve the problem efficiently when I ignore some of the input parameters?
2. What happens when I set some of the input parameters to trivial values, such as 0 or 1? Does the problem become easier to solve?
3. Can I simplify the problem to the point where I can solve it efficiently? Is the problem now trivial or still interesting?
4. Once I know how to solve a certain special case, why can't this be generalized to a wider class of inputs?
5. Is my problem a special case of a more general problem in the catalog?

5. Which of the standard algorithm design paradigms are most relevant to my problem?

1. Is there a set of items that can be sorted by size or some key? Does this sorted order make it easier to find the answer?
2. Is there a way to split the problem in two smaller problems, perhaps by doing a binary search? How about partitioning the elements into big and small, or left and right? Does this suggest a divide-and-conquer algorithm?
3. Do the input objects or desired solution have a natural left-to-right order, such as characters in a string, elements of a permutation, or the leaves of a tree? If so, can I use dynamic programming to exploit this order?
4. Are there certain operations being repeatedly done on the same data, such as searching it for some element, or finding the largest/smallest remaining element? If so, can I use a data structure to speed up these queries? What about a dictionary/hash table or a heap/priority queue?
5. Can I use random sampling to select which object to pick next? What about constructing many random configurations and picking the best one? Can I use some kind of directed randomness like simulated annealing in order to zoom in on the best solution?
6. Can I formulate my problem as a linear program? How about an integer program?
7. Does my problem seem something like satisfiability, the traveling salesman problem, or some other NP-complete problem? If so, might the problem be NP-complete and thus not have an efficient algorithm? Is it in the problem list in the back of Garey and Johnson [GJ79]?

6. Am I still stumped?

1. Am I willing to spend money to hire an expert to tell me what to do? If so, check out the professional consulting services mentioned in Section .
2. Why don't I go back to the beginning and work through these questions again? Did any of my answers change during my latest trip through the list?

Problem solving is not a science, but part art and part skill. It is one of the skills most worth developing. My favorite book on problem solving remains Pólya's How to Solve It [Pol57], which features a catalog of problem solving techniques that are fascinating to browse through, both before and after you have a problem.

Next: Resources Up: Techniques Previous: Implementation Challenges

Algorithms
Mon Jun 2 23:33:50 EDT 1997