Are there any guidelines on how to decide algorithm strategy when approaching a problem?

Question

There are many different general strategies when designing algorithms for a problem like divide and conquer, greedy, dynamic programming, etc. I understand that it is not always obvious which to use for a problem. However, I am at a complete loss as to how to even begin to make educated guesses. I assume intuition plays a huge part in this, but is there a reasonably concise summary anywhere of characteristics of problems that make them suitable for certain algorithm strategies?

I am having trouble parsing the many often super verbose and lengthy books on the subject.

Thanks in advance!

Answer 1

My rules of thumb and advice are:

1. When you have a problem and you're not sure which paradigm might be applicable, try them all.

2. Practice, practice, practice. As you get more practice with algorithm design questions, you'll start to get a "sixth sense" (an intuition) for when a particular paradigm might be worth a try or not. It might be hard to articulate the exact criteria, but as you practice, you'll get better at learning when a problem "smells like" it might be suitable for dynamic programming, or for divide-and-conquer, or some other paradigm.

3. Know the systematic approach for each paradigm, and try each one.

   • For greedy algorithms, there are usually only a few plausible greedy algorithms. It's usually pretty quick to try them all and rule them all out by finding small counterexamples or trying random testing. See How to prove greedy algorithm is correct. If you can't quickly prove that some strategy doesn't work by searching for small counterexamples and random testing, then it's worth spending serious effort to try to prove it correct. Basically, greedy algorithms almost never work; and when greedy algorithms are applicable, it's usually pretty easy to come up with a candidate greedy strategy that will work if anything does.

   • For dynamic programming algorithms, use the "follow your nose" approach articulated at https://cs.stackexchange.com/tags/dynamic-programming/info. Dynamic programming is likely to be a good bet if you can identify subproblems, and when solutions to the subproblems might help you solve the original problem. Dynamic programming is often worth a try when the inputs are strings or lists or trees. There might be multiple ways you can define simpler subproblems, and it may take some cleverness to figure out how to use solutions to the simpler subproblems to solve the original problem. Here it helps if you've practiced a lot with using recursion to solve problems, as dynamic programming is in some sense a sped-up form of a naive recursive algorithm.

   • For divide-and-conquer algorithms, usually it's pretty obvious if divide-and-conquer might be applicable. Is there a way you can split up the original problem into two pieces, so that if you knew the solution for each piece, you could combine those solutions into a solution for the original problem? In some sense you can view divide-and-conquer algorithms as an easy special case of dynamic programming.

   • There's one more very common paradigm, which is to reduce the problem to some other task you've already learned how to solve. For instance, reduce the problem to graph reachability, to linear programming, to max flow, to bipartite matching, or any of a number of other standard algorithmic problems.

Answer 2

The design of algorithms essentially rests on the properties of the problem addressed. These range from elementary to highly sophisticated.

Examples:

• Computing the sum of a sequence exploits associativity of addition, so that accumulation to a single variable is possible (this can be seen as an elementary greedy process).

• Sorting an array can rely on different facts:

  • you can sort an array by exchanging pairs made of a large element followed by a small element. Any exchange brings you closer to the sorted array, and exchanges can be done in any order. A possible implementation is by brute force (BubbleSort f.i.).

  • you can sort an array by partitioning it so that the small elements precede the large ones and sorting every partition independently. The partition sizes are free. The partitioning process can be simpler than sorting. This leads to QuickSort but also StraightSelectionSort.

  • you can sort an array by sorting subarrays then merging them. The subarray sizes are free. The merging process is easier than sorting. This leads to MergeSort, but also StraightInsertionSort.

  • A heap data structure can be useful for sorting, as it allow to implement a priority queue. You get a sorted sequence by popping all elements from the queue (HeapSort).

• Solving a nonlinear equation can be done by successive approximations:

  • If the function is continuous and a change of sign is known in an interval, then if you split the interval one of the subintervals will certainly exhibit a change of sign. The fastest way to subdivide intervals is by halving (Dichotomic method).

  • If the function is smooth, the tangent to the curve can be a good approximation and the intercept with the X axis is an approximation of a root.

And so on...