patterns & tips
patterns & tips
- Divide-and-Conquer: Can you divide the problem into two or more smaller independent subproblems and solve the original problem using solutions to the subproblems?
- Recursion, dynamic programming: If you have access to solutions for smaller instances of a given problem, can you easily construct a solution to the problem?
- Case analysis: Can you split the input/execution into number of cases and solve each case in isolation?
- Generalization: Is there a problem that subsumes your problem and is easier to solve?
- Data-structures: Is there a data-structure that directly maps to the given problem?
- Iterative refinement: Most problems can be solved using brute-force approach. Can you formalize such a solution and improve upon it.
- Small examples: Can you find a solution to small concrete instances of the problem and then build a solution that can be generalized to arbitrary instances?
- Reduction: Can you use a problem with a known solution as a subroutine?
- Graph modeling: Can you describe your problem using a graph and solve it using an existing algorithm?
- Write an equation: Can you express relationships in your problem in the form of equations (or inequalities)?
- Auxiliary elements: Can you add some new element to your problem to get closer to a solution?
- Variation: Can you solve a slightly different problem and map its solution to your problem?
- Parallelism: Can you decompose your problem into subproblems that can be solved independently on different machines?
- Caching: Can you store some of your computation and look it up later to save work?
- Symmetry: Is there symmetry in the input space or solution space that can be exploited?