If I had a machine with multiple processors and trying to solve a huge problem, which algorithm would be best for solving this problem?
Dynamic Programming, Greedy or the Divide and Conquer algorithm?
This is an extremely broad question, and many things will depend on the specific problem you're trying to solve, but what you're looking for is whether an algorithm can run its steps in parallel. This can only be done if the result of one step does not depend on the result of another.
- We can't say anything about greedy algorithms here. They're only defined as taking the locally best next step.
- Divide and conquer divides the problem into separate parts, each of which can be individually solved, so this is often a good candidate for running things in parallel.
- Dynamic programming could be viewed as a sort of divide and conquer, but now, you're solving a small part of the problem, and then using that to solve a bigger part, and so on. For example, the knapsack problem is often used as a use case for dynamic programming. You can solve the problem starting with a trivially small knapsack, and building up your solution from there. The problem here is that each solution depends on the solution of the smaller problem. Unless individual steps can be divided among threads, this cannot be parallelized.
So generally, divide and conquer seems to be your best bet for running things in parallel.