2022-03-11

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?